On rich 2-to-1 games

Mark Braverman, Subhash Khot, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 [16, 6, 5, 17], 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.

Original languageEnglish (US)
Title of host publication12th Innovations in Theoretical Computer Science Conference, ITCS 2021
EditorsJames R. Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771771
DOIs
StatePublished - Feb 1 2021
Event12th Innovations in Theoretical Computer Science Conference, ITCS 2021 - Virtual, Online
Duration: Jan 6 2021Jan 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume185
ISSN (Print)1868-8969

Conference

Conference12th Innovations in Theoretical Computer Science Conference, ITCS 2021
CityVirtual, Online
Period1/6/211/8/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • PCP
  • Perfect completeness
  • Unique-games

Fingerprint

Dive into the research topics of 'On rich 2-to-1 games'. Together they form a unique fingerprint.

Cite this