TY - GEN
T1 - On rich 2-to-1 games
AU - Braverman, Mark
AU - Khot, Subhash
AU - Minzer, Dor
N1 - Publisher Copyright:
© Mark Braverman, Subhash Khot, and Dor Minzer.
PY - 2021/2/1
Y1 - 2021/2/1
N2 - 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.
AB - 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.
KW - PCP
KW - Perfect completeness
KW - Unique-games
UR - http://www.scopus.com/inward/record.url?scp=85115275913&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115275913&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2021.27
DO - 10.4230/LIPIcs.ITCS.2021.27
M3 - Conference contribution
AN - SCOPUS:85115275913
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 12th Innovations in Theoretical Computer Science Conference, ITCS 2021
A2 - Lee, James R.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 12th Innovations in Theoretical Computer Science Conference, ITCS 2021
Y2 - 6 January 2021 through 8 January 2021
ER -