Learning and Lower Bounds for AC 0 with Threshold Gates
From MaRDI portal
Publication:3588437
DOI10.1007/978-3-642-15369-3_44zbMath1305.68106OpenAlexW1568706289MaRDI QIDQ3588437
Parikshit Gopalan, Rocco A. Servedio
Publication date: 10 September 2010
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_44
computational learning theorypolynomial threshold functionsthreshold gatesFourier concentrationAC\(^{0}\)
Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ The communication complexity of addition ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ Mining circuit lower bound proofs for meta-algorithms
This page was built for publication: Learning and Lower Bounds for AC 0 with Threshold Gates
