PCPs and Global Hyper-contractivity 1
summary
Label-cover is formalized with bipartite alphabets and projection constraints and is NP-hard to distinguish full satisfiability from ≤1−ε for constant alphabet via PCP. The unique games conjecture posits hardness even distinguishing ≥1−ε from ≤ε for matching constraints; a near-equivalent positive result holds for 2-to-1 games giving NP-hardness between 1/2 and ε. Analysis tools cited include hypercontractivity and the majority is stablest theorem. Two-query local testers force a test graph to be a small-set expander, or else a patched counterexample breaks soundness.
AI-written summary · about