Cancelled: Irit Dinur: Grassmann agreement testing and the 2:1 conjectureThis event has been cancelled.
Irit Dinur, Prof. Computer Science, Weizmann Institute of Science
Date: Tuesday, March 14, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Location: Patil/Kiva G449
Host: Ankur Moitra
Contact: Deborah Goodwin, 617.324.7303, email@example.com
Speaker URL: None
TALK: 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
Created by Deborah Goodwin at Wednesday, March 08, 2017 at 6:50 AM.