MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

TCS+ talk: 2-to-2 Games via expansion on the Grassmann Graph

Dor Minzer
Tel-Aviv University
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Wednesday, 14 February 2018
19:00
60 Minutes
E1 4
D1 Rotunda
Saarbrücken

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.

NOTE: This talk is streamed via Google Hangouts.

Contact

André Nusser
--email hidden
passcode not visible
logged in users only

André Nusser, 02/12/2018 10:31 -- Created document.