On Rich 2 -to- 1 Games

摘要

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, 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.