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: https://drops.dagstuhl.de/opus/volltexte/2021/13566/
Go to the corresponding LIPIcs Volume Portal


Braverman, Mark ; Khot, Subhash ; Minzer, Dor

On Rich 2-to-1 Games

pdf-format:
LIPIcs-ITCS-2021-27.pdf (0.6 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI