Constraint Satisfaction and Expansion

on YouTube ↗01h 01m

" summary

PCP-based reductions produce instances whose value is either 1 or bounded away from 1 (classically 7/8 for 3-SAT), using two routes: an algebraic encoding into low-degree polynomials and line-restrictions whose intersecting-line graph expands, and a combinatorial PCP gap amplification step that replaces vertices by neighborhoods and relies on edge expansion. Planted 3-SAT stays hard up to densities ≈N^{1/2} and fools SDP/SOS hierarchies, whereas planted coloring is recoverable at constant density via Alon–Kahale spectral recovery. Complexity often appears tied to the label-extended graph and to subtler expansion notions (splittable tuples, high-dimensional expanders).

AI-written summary · about

" chapters (19)

1. 0:00Start
2. 0:49Eric Diener
3. 2:41Constraint Satisfaction Problem
4. 3:30Graph Coloring
5. 5:54The Structure of the Csp
6. 6:17The Factor Graph
7. 8:03Constrained Hypergraph
8. 11:46Property of Graph Expansion
9. 14:13Pcp Theorem
10. 17:33The Proof of the Pcp Theorem
11. 18:21The Algebraic Proof
12. 19:33The Combinatorial Proof
13. 21:38Conclusion
14. 26:24Random Instances
15. 27:56Planted Random Preset
16. 29:56Coloring Csp
17. 44:09Label Extended Graph
18. 46:49Regularity Limits
19. 48:25Splitable Tuples