Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates

DOI10.1007/978-3-642-22935-0_54zbMath1343.68098MaRDI QIDQ3088133

Srikanth Srinivasan, Shachar Lovett

Publication date: 17 August 2011

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-22935-0_54

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

New algorithms and lower bounds for circuits with linear threshold gates, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, Unnamed Item, Unnamed Item, Unnamed Item, Near-optimal pseudorandom generators for constant-depth read-once formulas, Unnamed Item, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Estimation of certain exponential sums arising in complexity theory
• On the power of small-depth threshold circuits
• Pseudorandom bits for constant depth circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Majority gates vs. general weighted threshold gates
• The expressive power of voting polynomials
• Hardness vs randomness
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Complex polynomials and circuit lower bounds for modular counting
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• Learning and Lower Bounds for AC 0 with Threshold Gates
• On the Power of Threshold Circuits with Small Weights
• Communication Complexity
• Mathematical Foundations of Computer Science 2004
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Automata, Languages and Programming