Learning Read-Constant Polynomials of Constant Degree Modulo Composites

DOI10.1007/978-3-642-20712-9_3MaRDI QIDQ3007614zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Learning read-constant polynomials of constant degree modulo composites
• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• Multilinear polynomials modulo composites
• Composition modulo powers of polynomials
• Computing modular polynomials in quasi-linear time
• Algorithm for studying polynomial maps and reductions modulo prime number
• Computing Modular Polynomials
• A POLYNOMIAL ALGORITHM FOR TESTING CONGRUENCE MODULARITY
• Bivariate polynomials modulo composites and their applications
• Fast polynomial factorization and modular composition

Cites work

• 3-query locally decodable codes of subexponential length
• A lower bound on the MOD 6 degree of the OR function
• An Algebraic Perspective on Boolean Function Learning
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Estimation of certain exponential sums arising in complexity theory
• Finite monoids and the fine structure of NC ¹
• scientific article; zbMATH DE number 4041299 (Why is no real title available?)
• scientific article; zbMATH DE number 67609 (Why is no real title available?)
• scientific article; zbMATH DE number 1332656 (Why is no real title available?)
• Learning functions represented as multiplicity automata
• Learning matrix functions over rings
• Learning read-once formulas with queries
• 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
• Multilinear polynomials modulo composites
• Non-uniform automata over groups
• On Learning Read-k-Satisfy-j DNF
• Pseudorandom generators for group products, extended abstract
• Pseudorandom generators for regular branching programs
• Representing Boolean functions as polynomials modulo composite numbers
• Superlinear lower bounds for bounded-width branching programs

Cited in

(2)

• Learning matrix functions over rings
• Learning read-constant polynomials of constant degree modulo composites

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007614)