ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-151 | 6th December 2012 06:50

The Complexity of Somewhat Approximation Resistant Predicates

RSS-Feed




Revision #1
Authors: Subhash Khot, Madhur Tulsiani, Pratik Worah
Accepted on: 6th December 2012 06:51
Downloads: 329
Keywords: 


Abstract:

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-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 $\tau(f)$ denote the supremum over all $\tau$ 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} $(\tau(f) - \frac{|f^{-1}(1)|}{2^k})$ up to a factor of $O(k^5)$. We also give a similar characterization of the {\it integrality gap} for the natural SDP relaxation of MAX-$k$-CSP$(f)$ after $\Omega(n)$ rounds of the Lasserre hierarchy.



Changes to previous version:

Added an appendix with an improved version of Theorem 4.2, relating Fourier mass above level r to the distance from the set of Boolean functions with Fourier degree at most r.


Paper:

TR12-151 | 6th November 2012 00:24

The Complexity of Somewhat Approximation Resistant Predicates


Abstract:

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-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 $\tau(f)$ denote the supremum over all $\tau$ 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} $(\tau(f) - \frac{|f^{-1}(1)|}{2^k})$ up to a factor of $O(k^5)$. We also give a similar characterization of the {\it integrality gap} for the natural SDP relaxation of MAX-$k$-CSP$(f)$ after $\Omega(n)$ rounds of the Lasserre hierarchy.



ISSN 1433-8092 | Imprint