TY - GEN

T1 - A characterization of strong approximation resistance

AU - Khot, Subhash

AU - Tulsiani, Madhur

AU - Worah, Pratik

PY - 2014

Y1 - 2014

N2 - For a predicate f : {-1; 1}κ →{0; 1} with ρ(f) = |f-1(1)|/2κ we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [ρ(f)-Ω(1); ρ(f) +Ω(1)].We present a characterization of strongly approximation resistant predicates under the Unique Games Conjecture. We also present characterizations in the 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 on a natural convex polytope associated with the predicate. The predicate is called approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is at least ρ(f) +Ω(1). When the predicate is odd, i.e. f(-z) = 1-f(z); ∀z ∈ {-1; 1}κ, it is easily observed that the notion of approximation resistance coincides with that of strong approximation resistance. Hence for odd predicates our characterization of strong approximation resistance is also a characterization of approximation resistance.

AB - For a predicate f : {-1; 1}κ →{0; 1} with ρ(f) = |f-1(1)|/2κ we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [ρ(f)-Ω(1); ρ(f) +Ω(1)].We present a characterization of strongly approximation resistant predicates under the Unique Games Conjecture. We also present characterizations in the 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 on a natural convex polytope associated with the predicate. The predicate is called approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is at least ρ(f) +Ω(1). When the predicate is odd, i.e. f(-z) = 1-f(z); ∀z ∈ {-1; 1}κ, it is easily observed that the notion of approximation resistance coincides with that of strong approximation resistance. Hence for odd predicates our characterization of strong approximation resistance is also a characterization of approximation resistance.

KW - Approximation resistance

KW - Constraint satisfaction problems

KW - Integrality gaps

UR - http://www.scopus.com/inward/record.url?scp=84904329102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904329102&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591817

DO - 10.1145/2591796.2591817

M3 - Conference contribution

AN - SCOPUS:84904329102

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 634

EP - 643

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -