Learning Read-Constant Polynomials of Constant Degree Modulo Composites

DOI10.1007/978-3-642-20712-9_3zbMath1330.68085OpenAlexW133418326MaRDI QIDQ3007614

Ricard Gavaldà, Arkadev Chattopadhyay, Denis Thérien, Kristoffer Arnsfelt Hansen

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/28159

Mathematics Subject Classification ID

Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Estimation of certain exponential sums arising in complexity theory
• Non-uniform automata over groups
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Learning matrix functions over rings
• A lower bound on the MOD 6 degree of the OR function
• Representing Boolean functions as polynomials modulo composite numbers
• Superlinear lower bounds for bounded-width branching programs
• Pseudorandom Generators for Regular Branching Programs
• An Algebraic Perspective on Boolean Function Learning
• Finite monoids and the fine structure of NC ¹
• Learning read-once formulas with queries
• On Learning Read-k-Satisfy-j DNF
• Learning functions represented as multiplicity automata
• 3-query locally decodable codes of subexponential length
• Pseudorandom generators for group products
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Learning Read-Constant Polynomials of Constant Degree Modulo Composites