Name
Abstract | ||
|---|---|---|
A predicate f:{-1,1}^k -> {0,1} with \rho(f) = \frac{|f^{-1}(1)|}{2^k} is called {\it approximation resistant} if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment that satisfies at least \rho(f)+\Omega(1) fraction of the constraints. We present a complete characterization of approximation resistant predicates under the Unique Games Conjecture. We also present characterizations in the {\it mixed} linear and semi-definite programming hierarchy and the Sherali-Adams linear programming hierarchy. In the former case, the characterization coincides with the one based on UGC. Each of the two characterizations is in terms of existence of a probability measure with certain symmetry properties on a natural convex polytope associated with the predicate. |
Year | Venue | Field |
|---|---|---|
2013 | Electronic Colloquium on Computational Complexity (ECCC) | Discrete mathematics,Combinatorics,Unique games conjecture,Probability measure,Convex polytope,Omega,Linear programming,Predicate (grammar),Hierarchy,Mathematics |
DocType | Volume | Citations |
Journal | 20 | 2 |
PageRank | References | Authors |
0.40 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Subhash Khot | 1 | 2064 | 112.51 |
| Madhur Tulsiani | 2 | 358 | 24.60 |
| Pratik Worah | 3 | 51 | 8.90 |