CS Events Monthly View

The Unique-Games Conjecture (UGC) is a central open problem in Hardness of Approximation with wide array of implications; the 2-to-1 Games Conjecture is a closely related variant of UGC that has been recently proved.

In this talk, we will discuss a variant of the 2-to-1 Games Conjecture, called the Rich 2-to-1 Games Conjecture, and show that it is equivalent to UGC. We are motivated by two considerations.
Firstly, in light of the recent proof of the 2-to-1 Games Conjecture, we hope to understand how one might make further progress towards UGC. Secondly, in contrast to UGC, one may also consider the perfect completeness version of the new conjecture, which may imply new hardness of approximation results for problems that require perfect completeness (and hence are not implied by UGC).

No special background is assumed.

Based on a joint work with Mark Braverman and Subhash Khot