Past Events

Seminar

On Rich 2-to-1 Games

 

Download as iCal file

Wednesday, November 06, 2019, 09:45am

 

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

Speaker: Dor Minzer

Location : CoRE A 301

Committee

Rutgers/DIMACS Theory of Computing Seminar

Event Type: Seminar

Organization

Institute for Advanced Study