Inapproximability of Constraint Satisfaction Problems III
summary
Reduction starts from label cover and encodes labels by long codes, analyzes Fourier coefficients and probabilistic labelings to turn a parity test into an OR-style Max-3-Set predicate while keeping completeness and soundness gaps. The proof smooths the label cover, mixes many small Delta distributions to neutralize bad projection sizes, and bounds Fourier terms so large betas contribute negligibly. It also shows a gadget reduction to Max-2-Set giving 55/56 hardness via a 7‑clauses versus 6‑clauses tradeoff and the 7/8 baseline.
AI-written summary · about
chapters (14)
- 0:00Label cover and parity intro
- 3:59Homework review: three-set protocol
- 10:58Estimating problematic terms
- 21:57Controlling large and small sets in the analysis
- 28:42Solving bad size intervals
- 37:34Smoothness via label cover
- 47:23Estimating hard term
- 56:23Proof strategy and mapping
- 1:00:05Homework: four-set and four-Lin
- 1:03:38Summary and gadgets
- 1:04:47Two-Lin and gadget reductions
- 1:07:18Optimal gadget properties
- 1:12:12Gadget reduction ratio
- 1:15:32Q&A
related talks
54mConstraints, Gadgets, and Invariants
56mApproximate Counting II
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
58mRandom Constraint Satisfaction Problems
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
58mDichotomy Theorems for Counting Problems II
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
01h 02mApproximate Counting I