A characterization of strong approximation resistance

Subhash Khot, Madhur Tulsiani, Pratik Worah

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages634-643
Number of pages10
ISBN (Print)9781450327107
DOIs
StatePublished - 2014
Event4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States
Duration: May 31 2014Jun 3 2014

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other4th Annual ACM Symposium on Theory of Computing, STOC 2014
CountryUnited States
CityNew York, NY
Period5/31/146/3/14

Keywords

  • Approximation resistance
  • Constraint satisfaction problems
  • Integrality gaps

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A characterization of strong approximation resistance'. Together they form a unique fingerprint.

  • Cite this

    Khot, S., Tulsiani, M., & Worah, P. (2014). A characterization of strong approximation resistance. In STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing (pp. 634-643). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/2591796.2591817