On the Effect of Randomness on Planted 3-Coloring Models

on YouTube ↗42m

" summary

Framework plants a 3‑coloring P inside a host H, removes monochromatic edges, and asks for a legal 3‑coloring of the resulting G. Main positive claim: running spectral clustering then local improvements, cautious uncoloring, safe recoloring and dynamic programming recovers a legal coloring whenever P is random and H is an expander (second eigenvalue ≪ D); with D ≥ c log n it succeeds w.h.p. Main negative claim: if P is adversarial (even on random G(n,D)) completion becomes NP‑hard for D between n^0.4 and n^0.5 under the given reductions.

AI-written summary · about

" chapters (29)

1. 0:00Intro
2. 0:42NP-hard problems
3. 1:07Hosted coloring framework
4. 2:03illegal - monochromatic edges
5. 2:20The algorithmic challenge
6. 2:54Different models within the framework
7. 3:32The random planted 3-coloring model
8. 6:23Our questions
9. 7:06Outline of talk
10. 7:35Notions of coloring
11. 9:55Steps of Alon-Kahale algorithm
12. 13:14Local improvement
13. 14:05Cautious uncoloring
14. 15:09Dynamic programming
15. 16:14A legal coloring
16. 17:30Does the host graph need to be random? • The first step (spectral clustering) hinges on
17. 18:10Algorithm for 3-coloring with spectral expander host graph
18. 18:59The safe O(B)-partial coloring
19. 19:46Even if connected components of free vertices have arbitrary sizes, we complete the partial coloring to a legal one
20. 19:58Safe recoloring
21. 23:46Good and bad vertices
22. 24:33Algorithm for 3-coloring: adversarial expander Hand adversarial P
23. 25:58Running time
24. 26:24Main hardness result
25. 27:56Proof sketch
26. 29:02Input to ALG
27. 30:22Is H a random graph?
28. 33:20Spectral Techniques
29. 34:14Open questions