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
Seminar group:
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.
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.
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.
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).
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.