Dor Minzer: 2-to-2 Games is NP-hard

Wednesday, April 11, 2018 - 4:15pm to 5:15pm
Refreshments: 
Light Refreshments at 4:00
Location: 
STAR - D463
Speaker: 
Dor Minzer, Tel Aviv University
Abstract:
The PCP theorem characterizes the computational class NP, 
so as to facilitate proofs that approximation problems are NP-hard.
It can be viewed as a significant strengthening of the famous Cook-Levin theorem, 
stating that the problem of deciding the satisfiability of a given CNF formula is NP-complete.  
 
A fundamental open question in PCP theory is whether a special type of PCP, 
namely, 2-to-2-Games, is still NP-hard.  This conjecture is a variant of Khot's well-known Unique-Games Conjecture.
 
A recent line of study pursued a new attack on the 2-to-2 Games Conjecture (albeit with imperfect completeness). 
The approach is based on a mathematical object called the Grassmann Graph, and relies on the study of edge-expansion in this graph.
More specifically, the study of sets of vertices in the Grassmann Graph that contain even a tiny fraction of the edges incident to the set. 
 
A characterization of such sets was recently accomplished, completing a
proof for the 2-to-2 Games Conjecture (with imperfect completeness).
 
The talk discusses the 2-to-2 Games Conjecture, its implications and the line of study.
 
Based on joint works with Irit Dinur, Subhash Khot, Guy Kindler and Muli Safra.