Inapproximability of Constraint Satisfaction Problems V
summary
Argues that standard gadget/LP methods cannot prove NP-hardness for the sparse Hadamard predicate H7 and instead uses a construction that takes product-of-proof-systems to make bad Fourier terms handled, turning each problematic character into one controlled by some copy. Shows H7 is tricky: it has 8 accepting assignments, 120 auxiliary variables in the natural gadget, and naive hand verification fails. Also proves a separate combinatorial result: k-set with requirement L is easy if L>k/2 but NP-hard (e.g. 2-of-5) by long-code tests that force functions to depend on ≤3 coordinates.
AI-written summary · about
chapters (8)
- 0:00Gadget reductions and MP hardness
- 4:43Hadamard predicate H7
- 10:55MP hardness for H7 seemed hopeless
- 24:47Product of proof systems
- 39:55Terms in different proof systems
- 42:30k-set formula approximability
- 53:06Two out of five set formula hardness
- 1:16:21Summary and open problems
related talks
54mConstraints, Gadgets, and Invariants
47mNatural Proofs in Algebraic Circuit Complexity
57mTowards P≠NP from Extended Frege Lower Bounds
49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
01h 01mThe Gospel According to TCS
30mThe Hitting Proof System