An approach for 2-to-1 Games Conjecture via expansion on the Grassmann Graph

Abstract: The PCP theorem characterizes the computational class NP, so as to allow proving approximation problems are NP-hard.

One of the fundamental open questions in PCP theory is whether a special type of PCP, namely 2-to-1 Games, is still NP-hard. This conjecture is a variant of Khot's well-known Unique Games conjecture.

A recent line of study suggests a new attack on the 2-to-1 games conjecture (albeit with imperfect completeness). This approach is based on a mathematical object called the Grassmann Graph, and relies on an unproven combinatorial hypothesis on it. This, in turn, leads to the study of edge expansion in this graph. More specifically, to the study of sets of vertices in the Grassmann Graph, whose edge expansion is not optimal.

It turns out that the study of the combinatorial hypothesis is in fact equivalent to the study of edge expansion (Barak Kothari). Thus extending these results would complete the approach, proving that distinguishing between 2-to-1 games with close to 1 value, and 2-to-1 games with arbitrarily small value, is NP-hard.

This talk discusses this line of study.

Based on joint works with Irit Dinur, Subhash Khot, Guy Kindler and Muli Safra.