Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:TCS+ talk: 2-to-2 Games via expansion on the Grassmann Graph
Speaker:Dor Minzer
coming from:Tel-Aviv University
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Wednesday, 14 February 2018
Time:19:00
Duration:60 Minutes
Location:Saarbrücken
Building:E1 4
Room:D1 Rotunda
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
Name(s):André Nusser
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
André Nusser, 02/12/2018 10:31 AM
Last modified:
Uwe Brahm/MPII/DE, 02/14/2018 07:01 AM
  • André Nusser, 02/12/2018 10:31 AM -- Created document.