pdf icon
Volume 21 (2025) Article 10 pp. 1-55
On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs
Received: December 8, 2020
Revised: February 27, 2024
Published: November 26, 2025
Download article from ToC site:
[PDF (593K)] [PS (3660K)] [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: G.2.2
AMS Classification: 06E30, 05C48

Abstract: [Plain Text Version]

$ $

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an $n$-vertex graph has an independent set of size $\left( 1- \frac{1}{\sqrt{2}} \right) n - o(n) $ or every independent set has size $o(n)$, and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor $\sqrt{2}-o(1)$.

This article initiates and serves as the first installment in a line of work by various subsets of the authors together with Dinur and Kindler (with additional contributions by Barak, Kothari, and Steurer (ITCS'19)) which led to a proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness), which in particular implies the NP-hardness results for independent set and vertex cover mentioned above.

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

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