Dor Minzer: 2-to-2 Games is NP-hard

Abstract:
The PCP theorem characterizes the computational class NP,
so as to facilitate proofs that approximation problems are NP-hard.
It can be viewed as a significant strengthening of the famous Cook-Levin theorem,
stating that the problem of deciding the satisfiability of a given CNF formula is NP-complete.

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

A recent line of study pursued a new attack on the 2-to-2 Games Conjecture (albeit with imperfect completeness).
The approach is based on a mathematical object called the Grassmann Graph, and relies on the study of edge-expansion in this graph.
More specifically, the study of sets of vertices in the Grassmann Graph that contain even a tiny fraction of the edges incident to the set.

A characterization of such sets was recently accomplished, completing a
proof for the 2-to-2 Games Conjecture (with imperfect completeness).

The talk discusses the 2-to-2 Games Conjecture, its implications and the line of study.

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