Inapproximability of Constraint Satisfaction Problems IV
summary
Recap of concrete hardness techniques: starts from label cover with smooth label cover and uses long‑code style tests plus gadget reductions that introduce at most four auxiliary bits per clause; gadgets are found by a gadget LP over a finite set of candidate equations. Gives explicit gaps: a 3‑variable gadget with 16 equations achieves 12 vs 10 satisfiable so NP‑hardness ≈ 11/12 for the target, a Max‑Cut gadget reaches 16/17, and parameter dependencies blow up from polynomial to towers; unique‑games would simplify but remains open.
AI-written summary · about
chapters (10)
- 0:00Recap of label cover
- 1:37Max not two predicate hardness
- 8:22Wider vs narrower predicates
- 13:06Three set to two set reduction
- 27:17Gadgets via linear programming
- 42:31Improving gadget reductions
- 57:06Parity predicate uselessness
- 1:04:49Sparse predicates hardness
- 1:17:12Max two Lin false equations
- 1:22:28Future directions
related talks
54mConstraints, Gadgets, and Invariants
56mApproximate Counting II
01h 01mThe Gospel According to TCS
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
01h 07mWhere the Hard Things Are
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
47mNatural Proofs in Algebraic Circuit Complexity
47mRange Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms