Family 105Theoretical computer scienceLeanNot yet digested
Perfect completeness for 2-to-1 games
Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational , it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted instances. The alphabet depends only on δ, and every right-hand label has exactly two preimages under each constraint map.
Manuscripts in this family · 1
Perfect completeness for 2-to-1 games
Sep 23, 2026·paper.pdfLean
We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational , it is NP-hard to distinguish satisfiable 2-to-1 games from games of value at most δ, with a fixed alphabet and an explicitly listed unweighted multiset of constraints.