pdf icon
Volume 21 (2025) Article 11 pp. 1-50
Towards a Proof of the $2$-to-$1$ Games Conjecture
Received: December 8, 2020
Revised: March 5, 2024
Published: November 26, 2025
Download article from ToC site:
[PDF (571K)] [PS (3412K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: probabilistically checkable proofs, Unique Games Conjecture, Grassmann graph
Categories: complexity, probabilistically checkable proofs, Unique Games Conjecture, Grassmann graph
ACM Classification: F.2.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

$ $

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the $2$-to-$1$ Games Conjecture, albeit with imperfect completeness. This paper presents the second installment in a line of work by various subsets of the authors (with additional contributions by Barak, Kothari, and Steurer (ITCS'19)), which led to a proof of the $2$-to-$2$ Games Conjecture.

-------------

A preliminary version of this paper appeared in the Proceedings of the 50th ACM Symposium on Theory of Computing (STOC'18).