首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
  • 本地全文:下载
  • 作者:Cenny Wenner
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Håstad established that any predicate P01m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang who showed the threshold result that if a predicate strictly contains parity of width at least three, then it is approximation resistant also for satisfiable instances, assuming the d-to-1 Conjecture. We extend modern hardness-of-approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove, subject only to = , the same approximation-resistance result for predicates of width four or greater.

  • 关键词:Approximation Resistance; correlations; d-to-1 conjecture; Invariance; Perfect Completeness; Smooth Label cover
国家哲学社会科学文献中心版权所有