首页    期刊浏览 2024年10月04日 星期五
登录注册

文章基本信息

  • 标题:Candidate Lasserre Integrality Gap For Unique Games
  • 本地全文:下载
  • 作者:Subhash Khot ; Dana Moshkovitz
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We propose a candidate Lasserre integrality gap construction for the Unique Games problem. Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution of the Unique Games Conjecture. We use a new encoding scheme that we call the real code. The real code has two useful properties: like the long code, it has a unique local test, and like the Hadamard code, it has the so-called sub-code covering property.

  • 关键词:Lasserre hierarchy ; PCP ; Sum of Squares ; Unique Games Conjecture
国家哲学社会科学文献中心版权所有