Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
From MaRDI portal
Publication:3088133
DOI10.1007/978-3-642-22935-0_54zbMath1343.68098OpenAlexW1645439286MaRDI 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Unnamed Item ⋮ Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
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
This page was built for publication: Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
