From Weak to Strong LP Gaps for all CSPs
summary
Shows how to convert integrality gaps for weak linear-programming relaxations of constraint satisfaction problems into gaps for much stronger LP hierarchies. Works for all CSPs and uses specific hierarchy/extended-formulation frameworks (LP hierarchies and extended formulations) to lift weak LP counterexamples to stronger levels, yielding quantitative stronger gap results.
AI-written summary · about
chapters (21)
- 0:00Intro
- 2:54Approximating Max-k-CSP.
- 3:31Characterizing approximability
- 3:52A dichotomy assuming the UGC
- 4:34An unconditional version for LPs
- 6:28(Linear) Extended formulations
- 7:34Integer Program for CSPS
- 8:38The Sherali-Adams LP hierarchy (t levels)
- 10:30A local distribution view
- 11:10The basic LP
- 12:20Inaccurate pictorial representations
- 12:48A more precise version
- 14:02What is a hard instance (c = 1)
- 15:55Intuition for the proof
- 16:45The gap construction
- 18:35Bounding OPT(0)
- 21:41Propagation on trees
- 23:20Breaking up the graph
- 24:36Subset consistent partioning schemes
- 26:43The dimensionality problem
- 28:31Open Problems