Inapproximability of Constraint Satisfaction Problems II
summary
Shows NP‑hardness of approximating Max‑3‑LIN/Max‑3‑SAT to within the usual constants (half+ε for 3‑LIN and approaching 7/8+ε for 3‑SAT) by starting from PCP theorem and a label‑cover instance, replacing labels with long code tables, designing a noisy three‑bit verifier, and analyzing acceptance via Fourier expansion (orthogonality) plus Cauchy‑Schwarz. Builds a deterministic reduction and a probabilistic labeling extractor; completeness is 1 and soundness forces a contradiction when acceptance exceeds the claimed threshold.
AI-written summary · about
chapters (9)
- 0:00Max 3 Lin and PCPs intro
- 10:20Completeness vs soundness in PCPs
- 20:16Label cover and long code
- 33:32Expanding acceptance probability
- 45:50Extracting labeling strategy
- 58:24Max 3 Lin to Max 3 Set
- 1:09:14Final verification test design
- 1:20:22New verification distribution analysis
- 1:28:59Homework and next steps
related talks
56mApproximate Counting II
47mRange Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
01h 02mApproximate Counting I
53mNew Lower Bounds and Derandomization for ACC, and a...
47mNatural Proofs in Algebraic Circuit Complexity
58mRandom Constraint Satisfaction Problems