首页    期刊浏览 2024年08月22日 星期四
登录注册

文章基本信息

  • 标题:A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover
  • 本地全文:下载
  • 作者:Joshua Brakensiek ; Venkatesan Guruswami
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. Our result provides some indication of the expressiveness and non-triviality of 2-to-2 constraints, given the close connections between dictatorship tests and satisfiability and approximability of CSPs.

  • 关键词:Constraint satisfaction problems ; Dictatorship Tests ; Fourier analysis ; Inapproximability ; noise stability ; Property Testing ; Unique Games Conjecture
国家哲学社会科学文献中心版权所有