Beyond Worst Case Analysis in Approximation

on YouTube ↗57m

" summary

Surveys five problems and gives concrete claims: Max‑3SAT is stuck at a 7/8 hardness threshold even for natural random formulas; Min‑Bisection and 3‑coloring become tractable on dense random or planted models via spectral and SDP methods; a planted anti‑geometric model for 3‑coloring resists existing SDP rounding and poses an explicit algorithmic gap; unique games are easier under several semi‑random generators; densest k‑subgraph improvements follow from detecting planted subgraphs by log‑density thresholds.

AI-written summary · about

" chapters (23)

1. 0:00Intro
2. 0:44Plan of talk
3. 1:06A question to keep in mind
4. 1:56Max 3-SAT
5. 2:49Random max-3SAT
6. 9:16Random instances of bisection
7. 12:09Other distributions of random graphs
8. 14:13Algorithmic connections
9. 15:19The load on edges in a spanning tree
10. 19:58Min 3-coloring
11. 21:41Vector 3-coloring
12. 25:20Number of colors used expressed as nº
13. 27:41Max 3-coloring
14. 31:32Random host graph H
15. 31:53Remove monochromatic edges
16. 32:03The algorithmic task
17. 32:24Random 3-colorable graphs
18. 34:45A challenge
19. 38:31A geometric question
20. 43:36Four semi-random models for unique games
21. 49:28Log-density
22. 52:12Open question
23. 54:50Summary