Wednesday, February 14, 2018
10:00 am
Annenberg 205

TCS+ talk

2-to-2 Games via expansion on the Grassmann Graph
Dor Minzer, Tel Aviv University

Abtract: A fundamental goal in the theory of PCPs asks whether a special type of PCP, namely 2-to-2 Games, exists. This is a variant of Khot's well-known Unique Games conjecture.

In this talk we will discuss a recent line of study establishing the 2-to-2 games conjecture, albeit with imperfect completeness.
At the heart of the approach lies an object called the Grassmann Graph, and a certain linearity test on it. This leads to the study of edge expansion in this graph, and in particular, the study of (small) sets of vertices in the Grassmann Graph, whose edge expansion is bounded away from 1.

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

Contact Bonnie Leung bjleung@caltech.edu
Add this event to my calendar