Search Mailing List Archives
[theory-seminar] Muli Safra - 2-to-2 Games is NP-hard
bspang at stanford.edu
Wed Oct 9 14:18:23 PDT 2019
Just a reminder that Muli’s talk is at 3pm in Gates 463A
On Oct 7, 2019, at 3:43 PM, Bruce Spang <bspang at stanford.edu<mailto:bspang at stanford.edu>> wrote:
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!
2-to-2 Games is NP-hard
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...
More information about the theory-seminar