Learning read-constant polynomials of constant degree modulo composites

DOI10.1007/s00224-013-9488-6zbMath1319.68118OpenAlexW2016687122MaRDI 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 learningmembership queriesmodular gatespolynomials over finite rings

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Exact learning from an honest teacher that answers membership queries

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\)
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Learning read-constant polynomials of constant degree modulo composites