License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.27
URN: urn:nbn:de:0030-drops-135666
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13566/
Braverman, Mark ;
Khot, Subhash ;
Minzer, Dor
On Rich 2-to-1 Games
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 [Subhash Khot et al., 2017; Irit Dinur et al., 2018; Irit Dinur et al., 2018; Subhash Khot et al., 2018], 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.
BibTeX - Entry
@InProceedings{braverman_et_al:LIPIcs.ITCS.2021.27,
author = {Mark Braverman and Subhash Khot and Dor Minzer},
title = {{On Rich 2-to-1 Games}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {27:1--27:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13566},
URN = {urn:nbn:de:0030-drops-135666},
doi = {10.4230/LIPIcs.ITCS.2021.27},
annote = {Keywords: PCP, Unique-Games, Perfect Completeness}
}
|
Keywords: |
|
PCP, Unique-Games, Perfect Completeness |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
