Approximations of Submodular, XOS and Self-Bounding Functions by Juntas

on YouTube ↗54m

" summary

Proves a real-valued Friedgut theorem and shows which influence norms control L2 approximation, using hypercontractive inequalities and a boosting lemma; connects self-bounding and concentration to small L1/Lp influences. Main claim: monotone submodular functions admit 1/ε^2-type juntas (with a log factor) while XOS/fractionally subadditive functions provably need exp(1/ε^2) variables — an exponential gap. Includes tribes-style lower bounds and implications for learning from random examples; proofs are constructive and rely on discrete derivatives and Fourier/degree truncation.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 4:23Free Goods Theorem
3. 8:56Class of Xos Functions
4. 16:46Discrete Submodular Function
5. 30:02The Proof of Free Goods Theorem
6. 33:15Why Is this Useful for Self Bounding Function
7. 42:56Application of the Ulema