Name
Abstract | ||
|---|---|---|
A boolean predicate f : {0, 1}(k) -> {0, 1} is said to be somewhat approximation resistant if for some constant tau > vertical bar f(-1)(1)vertical bar/2(k), given a tau-satisfiable instance of the MAX k-CSP( f) problem, it is NP-hard to find an assignment that 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 hardness gap (tau(f) - vertical bar f(-1)(1)vertical bar/2(k)) up to a factor of O(k(5)). We show that the hardness gap is determined by two factors: The nearest Hamming distance of f to a function g of Fourier degree at most 2, which is related to the Fourier mass of f on coefficients of degree 3 or higher. Whether f is monotonically below g. When the Hamming distance is small and f is monotonically below g, we give an SDP-based approximation algorithm and hardness results otherwise. We also give a similar characterization of the integrality gap for the natural SDP relaxation of MAX k-CSP(f) after Omega(n) rounds of the Lasserre hierarchy. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-662-43948-7_57 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Journal | 8572 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Subhash Khot | 1 | 2064 | 112.51 |
| Madhur Tulsiani | 2 | 358 | 24.60 |
| Pratik Worah | 3 | 51 | 8.90 |