Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[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