首页    期刊浏览 2025年06月15日 星期日
登录注册

文章基本信息

  • 标题:On Rich 2-to-1 Games
  • 本地全文:下载
  • 作者:Mark Braverman ; Subhash Khot ; Dor Minzer
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2021
  • 卷号:185
  • 页码:27:1-27:20
  • DOI:10.4230/LIPIcs.ITCS.2021.27
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:PCP; Unique-Games; Perfect Completeness
国家哲学社会科学文献中心版权所有