The Complexity of Distributions

on YouTube ↗55m

" summary

Characterization: any AC0 sampler whose output has min-entropy k > ~sqrt(n) is a convex combination of bit-block sources, so samplable distributions reduce to structured blocks; consequence: for many functions (error‑correcting codes, certain boolean extractors) any AC0 sampler has statistical distance exponentially close to 1 from the true distribution, and for input/output pairs one can force distance ≈ 1/2. Constructions: AC0 can generate input-parity pairs exactly and can sample near-uniform permutations via a cycle-encoding trick. Tools: random restrictions + the switch lemma, hypercontractivity/noise norms, and a polarization lemma for min-entropy that preserves output distribution while collapsing entropy.

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 0:51The complexity of distributions
3. 1:34Outline
4. 1:53Sampling Hamming slices
5. 7:15Bounded-depth circuits (AC)
6. 9:03AC° can sample
7. 11:43Sampling permutations in AC
8. 17:09AC° cannot sample
9. 31:30The effect of restrictions on entropy
10. 33:45Proof of isoperimetric inequality
11. 37:09Recap
12. 37:53Example
13. 39:19Polarizing min-entropy
14. 42:45Polarization lemma
15. 49:08Putting things together
16. 50:53More open problems and conclusion