Irit Dinur: Grassmann agreement testing and the 2:1 conjecture

Abstract:  I will describe the notion of agreement testing, which allows to deduce global structure from local agreement checks.
In retrospect, agreement testing theorems are a key combinatorial component in nearly all PCPs.

In a recent work we showed that if a certain agreement testing theorem on the Grassmann graph is true, then Khot's 2:1 conjecture holds with imperfect completeness. Namely, it is NP-hard to decide if a label cover instance with 2:1 constraints has value 1-ε​ or ε​. This directly implies a hardness gap of 1/2 vs. ε​ for unique games.

Our construction builds on the exciting recent work of Khot Minzer and Safra who showed sqrt 2 hardness for vertex cover follows from a related hypothesis on the Grassmann graph.
I will describe our construction and how it differs from standard label cover paradigm. I will then describe the agreement test on the Grassmann which is really a generalization of the plane vs. plane low degree test.

based on joint work with Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra