2026-07-23T10:34:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13566 2024-03-06T10:52:20Z ddc:004 open_access

On Rich 2-to-1 Games Braverman, Mark Khot, Subhash Minzer, Dor PCP Unique-Games Perfect Completeness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Braverman and Subhash Khot and Dor Minzer 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.27 urn:nbn:de:0030-drops-135666 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.27 eng https://creativecommons.org/licenses/by/3.0/legalcode