Speaker: 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

Public: Yes

Location: Patil/Kiva G449

Event Type:

Room Description:

Host: Ankur Moitra

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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

Research Areas:
None selected

Impact Areas:
None selected

Created by Deborah Goodwin at Wednesday, March 08, 2017 at 6:50 AM.