קולוקוויום בביה"ס למדעי המחשב - 2-to-2 Games is NP-hard

Abstract:

The PCP theorem characterizes the computational class NP, so as to facilitate proofs that approximation problems are NP-hard.

Over the last two and a half decades, the theory of PCP's has been vital in the proof of numerous NP-hardness results for approximation problems. Despite considerable efforts, however, several tight hardness of approximation results remain elusive via the PCP theorem and the body of accompanying set of techniques. In many such cases, the Unique-Games Conjecture, posed by Khot in 2002, can still be used, to obtain tight hardness results. Since its proposal, the Unique-Games Conjecture has been a prominent open problem in theoretical computer science, inspiring many connections between Complexity Theory, Geometry, Analysis and Probability.  

This conjecture is stronger than the more standard conjecture that P\neq NP, and its validity has been a matter of debate. One would therefore much rather prove the gold-standard of computational hardness, that of NP-hardness.

The main subject of the talk is the 2-to-2-Games Conjecture, a closely related conjecture also due to Khot, stating that 2-to-2 Games is NP-hard.

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.