A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
DOI10.1137/19M1276467OpenAlexW3198174523MaRDI QIDQ4957916
Nutan Limaye, Utkarsh Tripathi, Karteek Sreenivasaiah, S. Venkitesh, Srikanth Srinivasan
Publication date: 10 September 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1276467
explicit constructionsmultivariate polynomialscombinatorial designsconstant-depth circuitsJanson's inequalitycoin problem
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The average sensitivity of bounded-depth circuits
- Randomness buys depth for approximate counting
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
- Pseudorandom bits for constant depth circuits
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Families of finite sets in which no set is covered by the union of \(r\) others
- The monotone circuit complexity of Boolean functions
- A method for obtaining efficient lower bounds for monotone complexity
- The expressive power of voting polynomials
- Depth reduction for circuits of unbounded fan-in
- Hardness vs randomness
- A hierarchy for nondeterministic time complexity
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols
- On uniformity within \(NC^ 1\)
- The Difference Between Consecutive Primes, II
- BQP and the polynomial hierarchy
- Certifying polynomials for AC^0(parity) circuits, with applications
- Two Sides of the Coin Problem
- Constant depth circuits, Fourier transform, and learnability
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Poisson approximation for large deviations
- On the distribution of the number of roots of polynomials and explicit weak designs
- An Average-Case Depth Hierarchy Theorem for Boolean Circuits
- The Coin Problem for Product Tests
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Analysis of Boolean Functions
- A fixed-depth size-hierarchy theorem for AC 0 [⊕ via the coin problem]
- Computational Complexity
- On the Computational Complexity of Algorithms
- Hardness Amplification Proofs Require Majority
- Approximation by DNF: Examples and Counterexamples
- The NP-completeness column: An ongoing guide
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
