ECCC-Report TR13-146https://eccc.weizmann.ac.il/report/2013/146Comments and Revisions published for TR13-146en-usSat, 12 Apr 2014 01:05:32 +0300
Revision 1
| A Characterization of Approximation Resistance |
Subhash Khot,
Madhur Tulsiani,
Pratik Worah
https://eccc.weizmann.ac.il/report/2013/146#revision1This paper is withdrawn due to a bug in the trick for going from Strong Approximation Resistance to Approximation Resistance. The previous result for Strong Approximation Resistance still holds (see ECCC report TR13-075).Sat, 12 Apr 2014 01:05:32 +0300https://eccc.weizmann.ac.il/report/2013/146#revision1
Paper TR13-146
| A Characterization of Approximation Resistance |
Subhash Khot,
Madhur Tulsiani,
Pratik Worah
https://eccc.weizmann.ac.il/report/2013/146A predicate $f:\{-1,1\}^k \mapsto \{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.
This is a revised version of out previous paper which gave a characterization for a modified notion called "Strong Approximation Resistance".Tue, 22 Oct 2013 10:16:05 +0300https://eccc.weizmann.ac.il/report/2013/146