skip to main content

TCS+ Talk

Wednesday, February 14, 2018
10:00am to 11:00am
Add to Cal
Annenberg 205
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

For more information, please contact Bonnie Leung by email at [email protected].