Learning read-constant polynomials of constant degree modulo composites

DOI10.1007/s00224-013-9488-6zbMath1319.68118MaRDI QIDQ2254504

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

Publication date: 5 February 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

exact learning; membership queries; modular gates; polynomials over finite rings

Mathematics Subject Classification ID

68Q32: Computational learning theory

68Q25: Analysis of algorithms and problem complexity

Related Items

Exact learning from an honest teacher that answers membership queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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\)
• Complexity theoretic hardness results for query learning
• 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
• Read-twice DNF formulas are properly learnable
• 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