The 2-to-2 Games Theorem

Seminar: 
Combinatorics Seminar
Event time: 
Thursday, November 1, 2018 - 4:00pm
Location: 
DL 431
Speaker: 
Subhash Khot
Speaker affiliation: 
Courant Institute - NYU
Event description: 

I will present an overview of a recent proof of the 2-to-2 Games Theorem.
The proof has two parts: a construction of an appropriate PCP/reduction
and a structure theorem about “non-optimally expanding” sets in the
Grassmann graph; the latter is used to analyze the “soundness” of the
former.

Two interesting consequences (among several others) of the theorem are:

(1) Given an n-vertex graph that contains an independent set of size n/4,
it is NP-hard to find an independent set of size \eps n where \eps > 0 is
an arbitrarily small constant.

One also gets a coloring result: given an (almost) 4-colorable graph, it
is NP-hard to (almost) color it with constantly many colors.

(2) It, arguably, gives strong evidence towards the Unique Games
Conjecture. In a certain sense, it already goes “half-way” towards proving
the Unique Games Conjecture.

This is joint work with Irit Dinur, Guy Kindler, Dor Minzer, and Muli
Safra. It appears in a sequence of papers [ECCC Reports TR16-124,
TR16-198, TR17-094, TR18-006]. It also benefited from contributions in [K
Safra’11], [Barak Kothari Steurer’18], [K Minzer Moshkoviz Safra’18]

Research Area(s):