This event has been cancelled
Irit Dinur: Grassmann agreement testing and the 2:1 conjecture
Speaker
Irit Dinur, Prof. Computer Science, Weizmann Institute of Science
Host
Ankur Moitra
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
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