The long path to \sqrt{d} monotonicity testers

on YouTube ↗56m

" summary

Shows an almost-complete resolution: non-adaptive monotonicity testing on {n}^d uses √d query "path testers" that run short upward random walks (length ≈√d) and find a violation with ≈1/√d success per sampled pair. The analysis rests on directed isoperimetry: a robust Talagrand-type inequality that guarantees a regular bipartite subgraph in the directed boundary (≈2^d/r vertices of degree r^2), which makes the path-analysis work. Extensions reach hypergrids (poly(n) factors removed up to tiny o(1) losses); adaptive complexity remains open.

AI-written summary · about

" chapters (10)

1. 0:00Monotonicity testers intro
2. 1:05Boolean functions on hypergrids
3. 6:41Edge tester for hypercubes
4. 13:26From hypercubes to hypergrids
5. 23:55Directed isoperimetric theorems
6. 32:11Measuring Boolean boundaries
7. 40:04Talagrand inequality implications
8. 45:58Isoperimetry for monotonicity
9. 50:16Open questions and complexity
10. 53:13Q&A