Tight bounds on the Fourier spectrum of AC^0

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

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

(34)

A slight sharpening of LMN
Interactive proofs for social graphs
Expander-based cryptography meets natural proofs
Explicit two-source extractors and resilient functions
Harmonicity and invariance on slices of the Boolean cube
A simple proof of Bazzi's theorem
Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
On polynomial approximations to \(\mathrm{AC}^0\)
Pseudorandom functions: three decades later
Quantified Derandomization: How to Find Water in the Ocean
scientific article; zbMATH DE number 7528580 (Why is no real title available?)
Expander-Based Cryptography Meets Natural Proofs
On the probabilistic degree of OR over the reals
Criticality of regular formulas
Fourier bounds and pseudorandom generators for product tests
Near-optimal pseudorandom generators for constant-depth read-once formulas
scientific article; zbMATH DE number 7561745 (Why is no real title available?)
Improved pseudorandom generators from pseudorandom multi-switching lemmas
An Optimal Separation of Randomized and Quantum Query Complexity
On the probabilistic degree of OR over the reals
Influence of a Set of Variables on a Boolean Function
Paradigms for Unconditional Pseudorandom Generators
The work of Mark Braverman
Quantum cryptography in Algorithmica
A moment-matching approach to testable learning and a new characterization of Rademacher complexity
Limits of preprocessing
Pseudorandomness, symmetry, smoothing: I
A technique for hardness amplification against AC^0
KKL theorem for the influence of a set of variables
Parity vs. \(\text{AC}^0\) with simple quantum preprocessing
Comparing computational entropies below majority (or: when is the dense model theorem false?)
A lower bound on the trace norm of Boolean matrices and its applications
Testing isomorphism of Boolean functions over finite abelian groups

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)