Fooling Polytopes

on YouTube ↗46m

" summary

Constructs an explicit pseudorandom generator / discrepancy set that fools all M‑facet 0/1 polytopes in n dimensions with size roughly n^{polylog M} (for example poly(n)‑many facets gives quasi‑polynomial size), an exponential improvement over prior linear‑in‑M bounds. Proof mixes a heads‑and‑tails decomposition, a bucketing + k‑wise generator, a derandomized Lindeberg replacement and reductions to fooling CNF formulas, plus a new Boolean Littlewood‑Offord anti‑concentration bound; the generator is explicit and achieves the stated seed/size bounds, though epsilon dependence remains suboptimal.

AI-written summary · about

" chapters (26)

1. 0:00Intro
2. 0:16Polytopes over 0,1 = Intersections of boolean halfspaces
3. 1:27This talk: Discrepancy Sets for Polytopes
4. 2:33Pseudorandom Generators
5. 3:26Our main result: PRG for polytopes
6. 5:10Comparison with prior results
7. 7:31Structure of this talk
8. 9:04Central Limit Theorems
9. 9:49Regularity and the Berry-Esséen CLT
10. 11:23The connection between CLTs and pseudorandomness
11. 13:22Meka-Zuckerman's PRG for regular halfspaces
12. 18:53Main challenge: CLTs and regularity go hand in hand
13. 19:25This work: bypassing Gaussian middleperson (by necessity) Let A be general mx matrix
14. 20:22But-will still employ CLT proof techniques
15. 22:06Regularity lemma for a single halfspace
16. 25:20A smooth version of CDF distance
17. 26:38Smooth approximators of orthants Standard way of mollifying a function: adding Gaussian noise
18. 28:35Proving the smooth version via a hybrid argument
19. 31:33Single swap in the hybrid argument
20. 32:27Multidimensional Taylor expansion
21. 34:29Warmup: fooling the zeroth-order term
22. 36:35Back to the Taylor expansion
23. 39:45Another conceptual difference/challenger Boolean vs. Gaussian anticoncentration
24. 41:28A high-dimensional Littlewood-offord inequality
25. 43:10Recap of proof structure
26. 43:37Summary