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

文章基本信息

  • 标题:The Complexity of Somewhat Approximation Resistant Predicates
  • 本地全文:下载
  • 作者:Subhash Khot ; Madhur Tulsiani ; Pratik Worah
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    A boolean predicate f:01k01 is said to be {\em somewhat approximation resistant} if for some constant \frac{|f^{-1}(1)|}{2^k}">2kf−1(1), given a -satisfiable instance of the MAX-k-CSP(f) problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let (f) denote the supremum over all for which this holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates, we give a characterization of the {\it hardness gap} ((f)−2kf−1(1)) up to a factor of O(k5). We also give a similar characterization of the {\it integrality gap} for the natural SDP relaxation of MAX-k-CSP(f) after (n) rounds of the Lasserre hierarchy.

国家哲学社会科学文献中心版权所有