Structure Of Boolean Almost Low Degree Functions On The Biased Cube
summary
Claims precise structural descriptions: on the p‑biased cube any degree‑d real polynomial f that is ε‑close in L2 to Boolean has (after possibly negating) an explicit p‑biased FKN form: f is O(ε)-close to a sparse, quantized degree‑d polynomial whose support size and each link size are O(ε/p^e) (for d=1 this gives at most O(√ε/p+1) coordinates and O(√ε+p) closeness to a constant); on the symmetric group degree‑1 functions are O(√ε)-close to a row/column dictator and O(ε)-close to unions of nearly disjoint cosets. Proof builds a global g by sampling S ~ μ2p then y ~ μ1/2, applies FKN/Kindler–Safra and pastes via plurality/majority and agreement theorem arguments; the constructions yield the stated quantitative bounds and are tight up to constants.
AI-written summary · about
chapters (9)
- 0:00Introduction to Boolean closeness
- 3:24The FKN and Kindler-Safra theorems
- 7:01Input domains: biased cube and symmetric group
- 11:09P-biased FKN theorem
- 18:55Symmetric group analysis
- 23:26Stability and structural properties
- 36:10The degree D case
- 40:03Sparse constraints and minimal inputs
- 50:51Proofs and open questions
related talks
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
01h 00mAverage-case Complexity for Polynomials, and All That
19mCounterexamples to the Low-Degree Conjecture
50mAlgorithmic Regularity for Polynomials and Applications
39mOptimization over the Hypercube via Sums of Nonnegative Circuit Polynomials
57mIt ain't over till it's over
27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
01h 34mIntroduction to Analysis on the Discrete Cube IV