Reverse Hypercotractivity and Improved Sampling in High Dimensional Expanders

on YouTube ↗58m

" summary

Proves that many high-dimensional expanders satisfy reverse hypercontractivity by showing a concrete small-set mixing bound for two noise-like graphs (intersection-based J_{k,l} and coin-flip J_k^rho). For example with rho=1/4 and l = k/4, any A,B of size at least exp(-Omega(k)) have an edge probability at least (Pr[A] Pr[B])^{O(1)}. Proof uses sampler/containment graphs, a high-dimensional expander mixing lemma and a batching argument (j≈100, b=k/(4j)). Requires very strong expansion (lambda = exp(-Omega(k))) but the method succeeds under that assumption.

AI-written summary · about

" chapters (15)

1. 0:00Reverse hypercontractivity intro
2. 1:47High-dimensional expanders and simplicial complexes
3. 3:19Reverse hypercontractivity in expanders
4. 7:24Small-set mixing in expanders
5. 11:17History of reverse hypercontractive inequalities
6. 15:55Two-function reverse hypercontractivity
7. 19:34Mixing and sampling in expanders
8. 22:28Sampler graphs properties
9. 25:45Sampler graphs examples and bounds
10. 29:17Sampling in high-dim expanders
11. 33:50Proof sketch for reverse hypercontractivity
12. 37:10Batch sampling technique
13. 41:01Inductive argument with batch processing
14. 50:26Concluding remarks
15. 52:23Q&A