A Structure Theorem for Boolean Functions with Small Total Influences
summary
A structural theorem says Boolean functions on a product probability space with constant total influence are L2-close to a K-pseudo-junta defined by a family of local constraints, with K = exp(O((I/ε)^3)) (Boolean case improves to quadratic). Proof uses a truncated Fourier–Walsh decomposition, a Bourgain-type large-coefficient lemma relying on hypercontractivity, and carefully constructed constraint indicators JS; the construction yields the approximation and explains why small influence implies a small set of influential coordinates and hence sharp-threshold consequences.
AI-written summary · about
chapters (9)
- 0:00Start
- 1:31Some Examples
- 5:04Some background
- 8:02Thresholds
- 10:16Observation
- 24:56Generalized Walsh expansions
- 27:08Step 1: Eliminating High Frequencies
- 31:44Step IV: Bounding the error
- 39:11Open problem
related talks
45mA categorical view of computational effects
54mCategory Theory Through Functional Programming (part 3/3)
53mIntroduction to Intuitionistic Type Theory
25mLinear Types with Dynamic Multiplicities in Dependent Type Theory (Functional Pearl)
27mWith or Without You: Programming with Effect Exclusion
16mSensitivity by Parametricity
27mA General Fine-Grained Reduction Theory for Effect Handlers
01h 08mType Arithmetic and the Yoneda Lemma