Structure of the Fourier Spectrum of Boolean Functions and Complexity
summary
Claim: Boolean f with small spectral norm (L1 ≤ M) decomposes as a ± sum of indicators of affine subspaces (Green–Sanders), with number of terms bounded by a double-exponential function of M; this gives membership in AC0[⊕] and parity-based constructions. Proven bounds: parity decision tree size ≤ n^{O(M^2)} and DeMorgan formula size ≤ n^{O(M^2)} (depth O(log size)). For sparse f (s nonzero Fourier coefficients) conjecture is parity decision tree depth = polylog(s); rank(MF)=s for XOR matrices links this to the Log-Rank Conjecture. When both L1 ≤ M and sparsity s, depth ≤ O(M^2 log s).
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:25Outline
- 1:58Notation
- 3:04Just specular norm
- 3:55Indicators
- 5:02Theorem
- 6:02Complexity Class
- 10:50Parity Decisions
- 16:56Formula
- 22:47Address Function
- 24:50Communication Complexity
- 31:06Special Case
- 31:50Proof
- 36:02Summary
related talks
01h 01mTrue Complexity of Multilinear Systems
15mPolynomial Bounds of CFLOBDDs against BDDs
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
01h 01mTop-Down Lower Bounds for Depth-Four Circuits
49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
32mA Finite Alternation Result for Reversible Boolean Circuits
13mProgram Analysis via Efficient Symbolic Abstraction
32mReed-Muller and Other Subcodes of the Sierpinski Matrix