Tight bounds on the Fourier spectrum of AC^0

DOI10.4230/LIPICS.CCC.2017.15zbMATH Open1440.68084MaRDI QIDQ5111145FDOQ5111145

Authors: Avishay Tal 

Publication date: 26 May 2020

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

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)

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
• Title not available (Why is that?)
• Paradigms for Unconditional Pseudorandom Generators
• Limits of preprocessing
• Expander-based cryptography meets natural proofs
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the probabilistic degree of OR over the reals
• Pseudorandom functions: three decades later
• Quantified Derandomization: How to Find Water in the Ocean
• Explicit two-source extractors and resilient functions
• 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
• Title not available (Why is that?)

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)