Inapproximability of Constraint Satisfaction Problems I

on YouTube ↗01h 32m

" summary

Claim: it is NP‑hard to beat 7/8 hardness for MAX‑3SAT. Proof outline: reduction from satisfiability via the PCP theorem, then parallel repetition to get a Label Cover instance, encode labels with the long code, and run a three‑bit testing gadget (with folding) that yields a MAX‑3‑LIN/MAX‑3‑SAT instance whose completeness is near 1 and whose soundness forces only the random assignment ratio. Key technical step is the soundness lemma extracting a labeling from any high‑accepting proof.

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 1:47A Generic Constraint Satisfaction Problem
3. 3:29The Approximation Ratio
4. 21:31The Pcp Theorem
5. 22:56Pcp Theorem
6. 41:35Cherry Parallel Game

" related talks

• 31mNew Unconditional Lower Bounds for Algorithms and Enumeration ProblemsSerge Gaspers · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 27mOn the Subexponential Time Complexity of the CSPIyad Kanj · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related ProblemsMichał Pilipczuk · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 26mLower Bounds on the Running Time for Scheduling and Packing ProblemsKlaus Jansen · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 58mLower Bound Issues in Computational Social ChoiceRolf Niedermeier · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 30mLower Bound Results for Hard Problems Related to Finite AutomataHenning Fernau · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper BoundsMarcin Pilipczuk · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 33mSub-exponential Approximation Schemes for CSPs: from Dense to Almost SparseMichael Lampis · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms