Tight bounds on the Fourier spectrum of AC^0

DOI10.4230/LIPICS.CCC.2017.15MaRDI QIDQ5111145zbMATH OpenFDO

Authors Avishay Tal

Publication date 26 May 2020

zbMATH Keywords

Boolean circuitsFourier analysisbounded-depth circuits\(k\)-wise independenceswitching lemma

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• On polynomial approximations to \(\mathrm{AC}^0\)
• scientific article; zbMATH DE number 6861917
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Constant depth circuits, Fourier transform, and learnability
• \(\mathrm{AC}^0\circ\mathrm{MOD}_2\) lower bounds for the Boolean inner product

Cited in

(27)

• A simple proof of Bazzi's theorem
• Expander-Based Cryptography Meets Natural Proofs
• On polynomial approximations to \(\mathrm{AC}^0\)
• Interactive proofs for social graphs
• Criticality of regular formulas
• Fourier bounds and pseudorandom generators for product tests
• A slight sharpening of LMN
• Harmonicity and invariance on slices of the Boolean cube
• scientific article; zbMATH DE number 7561310 (Why is no real title available?)
• Paradigms for Unconditional Pseudorandom Generators
• Expander-based cryptography meets natural proofs
• Limits of preprocessing
• An Optimal Separation of Randomized and Quantum Query Complexity
• Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7650112 (Why is no real title available?)
• On the probabilistic degree of OR over the reals
• Pseudorandom functions: three decades later
• Explicit two-source extractors and resilient functions
• Quantified Derandomization: How to Find Water in the Ocean
• Influence of a Set of Variables on a Boolean Function
• The work of Mark Braverman
• A moment-matching approach to testable learning and a new characterization of Rademacher complexity
• Quantum cryptography in Algorithmica
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)

This page was built for publication: Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)

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