{"id":"openai-math/Perfect-completeness-for-2-to-1-games","pdf":"https://github.com/openai/math/blob/main/preprints/Perfect-completeness-for-2-to-1-games-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Perfect-completeness-for-2-to-1-games-September-23-2026","tags":["computational-complexity","pcp","unique-games"],"score":0,"title":"Perfect completeness for 2-to-1 games","domain":"Theoretical computer science","family":"105","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational $`\\delta\\in(0,1)`$, 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://gilkalai.wordpress.com/2026/10/07/updates-sharing-ai-progress-on-mathematics-amazing-and-my-lecture-plans/#:~:text=announces%20a%20proof%20of%20the%20Unique%20Games%20Conjecture","date":"2026-10-07","kind":"web","site":"Combinatorics and more","text":"announces a proof of the Unique Games Conjecture and, separately, the 2-to-1 Games Conjecture with perfect completeness . Matrix multiplication. My post Cap Sets, Sunflowers, and Matrix Multiplication explored the connections between these problems. The new bound is over the complex numbers , a…","added":"2026-10-24","title":"Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans"}],"formalized":true,"family_title":"Perfect completeness for 2-to-1 games"}