Current Developments in Mathematics

Volume 2019

On the proof of the 2-to-2 Games Conjecture

Pages: 43 – 94

DOI: https://dx.doi.org/10.4310/CDM.2019.v2019.n1.a2

Author

Subhash Khot (Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York, N.Y., U.S.A.)

Abstract

This article gives an overview of the recent proof of the 2‑to‑2 Games Conjecture in [68, 39, 38, 69] (with additional contributions from [75, 18, 67]). The proof requires an understanding of expansion in the Grassmann graph.

The 2‑to‑2 Games Conjecture is a lesser variant of the more wellknown Unique Games Conjecture in Theoretical Computer Science. These conjectures have applications to “hardness of approximation”, namely, the phenomenon that for many NP-hard problems, even computing approximate solutions to them remains NP-hard. They have several additional connections to computational complexity, algorithm design, analysis, and geometry.

The proof of the 2‑to‑2 Games Conjecture proves the Unique Games Conjecture “half-way” (at least in a certain technical sense) and in author’s opinion, provides a strong evidence in favor of the latter.

Full Text (PDF format)

Research supported by NSF grant CCF-1813438, Simons Collaboration on Algorithms and Geometry grant, and the Simons Investigator Award.

Published 13 October 2021