Search Mailing List Archives
[theory-seminar] Muli Safra - 2-to-2 Games is NP-hard
Bruce Spang
bspang at stanford.edu
Mon Oct 7 15:43:44 PDT 2019
Hi all,
For this week’s theory seminar, we have Muli Safra talking about "2-to-2 Games is NP-hard.” It will be on Wednesday 10/9 from 3-4pm in Gates 463A
The abstract is below. Hope to see you there!
Bruce
2-to-2 Games is NP-hard
Muli Safra
The PCP theorem characterizes the computational class NP, to facilitate proofs that almost all approximation problems are NP-hard. to within a ratio only slightly better than the the one known to be efficiently achievable. It can be viewed as a significant strengthening of the Cook-Levin theorem, which states that the problem of deciding the satisfiability of a given CNF formula is NP-hard. The PCP characterization asserts that even coming close to satisfying a given formula is NP-hard.
A fundamental open questions in PCP theory was whether a special type of PCP, namely, 2-to-2-Games, is still NP-hard. The conjecture stating it is NP-hard is a variant of Khot's infamous 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 (which requires Analysis of Boolean functions on steroids). 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 (albeit with imperfect completeness).
The talk discusses the 2-to-2 Games Conjecture, its implications and the line of study.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20191007/4213ea69/attachment.html>
More information about the theory-seminar
mailing list