Uniform brackets, containers, and combinatorial Macbeath regions

on YouTube ↗32m

" summary

Shows an equivalence: having ε‑containers or λ‑heavy ε M‑nets for both a set system and its complement suffices to produce uniform ε‑brackets, and vice versa, via recursive extraction plus δ‑covering and Haussler’s covering bound. Delivers distribution‑free upper bounds for points vs halfspaces of size O(ε^{-d}), constructive lower bounds Ω(ε^{-d/3}), and corollary communication complexity bounds like O(d log n) for learning halfspaces and O(d^2 log n) for convex disjointness.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:20Co-Authors
3. 0:32The Three Structures...
4. 3:34A Theorem of Macbeath
5. 4:40Macbeath's Theorem
6. 5:07Combinatorial Macbeath Regions (Mnets)
7. 6:17Mnets (contd.)
8. 8:13Uniform Brackets (contd.)
9. 9:01Uniform Brackets: Applications
10. 10:05Connections
11. 11:13Points and Haltspaces in R
12. 14:45New Results (contd.)
13. 15:38New Results: Applications
14. 18:39Small-set Containers: Extract and Recurse
15. 21:00Small-set Containers: Size
16. 22:18Size of Small-set Containers (contd.)
17. 24:10Removing log(1/6) from the Exponent
18. 26:18Brackets via Minimal Coverings
19. 29:52Brackets via Coverings (contd.)