文章基本信息

标题：Approximation Resistance on Satisfiable Instances for Sparse Predicates
本地全文：下载
作者：Sangxia Huang
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2014
卷号：10
页码：359-388
出版社：University of Chicago
摘要：For every integer $k \ge 3$, we prove that there is a predicate $P$ on $k$ Boolean variables with $2^{\widetilde{O}(k^{1/3})}$ accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint $P$, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Håstad and Khot ( Theory of Computing, 2005) who showed that a predicate on $k$ variables with $2^{O(k^{1/2})}$ accepting assignments is approximation resistant on satisfiable instances
关键词：Max-CSP; probabilistically checkable proofs; approximation resistance; satisfiable instance