首页    期刊浏览 2025年02月20日 星期四
登录注册

文章基本信息

  • 标题:On Rich 2 -to- 1 Games
  • 本地全文:下载
  • 作者:Mark Braverman ; Subhash Khot ; Dor Minzer
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-26
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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.

  • 关键词:hypercontractivity ; PCP ; Unique Game Conjecture
国家哲学社会科学文献中心版权所有