Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-141 | 22nd October 2019 05:36

On Rich $2$-to-$1$ Games

RSS-Feed




TR19-141
Authors: Mark Braverman, Subhash Khot, Dor Minzer
Publication: 24th October 2019 03:42
Downloads: 221
Keywords: 


Abstract:

We propose a variant of the $2$-to-$1$ Games Conjecture that we call the Rich $2$-to-$1$ Games Conjecture and show that it is equivalent to the Unique Games Conjecture. 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 a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture.



ISSN 1433-8092 | Imprint