[theory students] Theory lunch and TCS+ noon tomorrow 2310 (Dor Minzer)

[Benjamin Miller <bmiller@xxxxxxxxxxx>]

Hi all,

We'll have theory lunch and call in to the TCS+ talk tomorrow at noon. Dor Minzer will be presenting on "2-to-2 Games via expansion on the Grassmann Graph" (see abstract below).

We'll meet in 2310. As usual, bring your own lunch. See you there!

Benjamin



Title: 2-to-2 Games via expansion on the Grassmann Graph

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