### 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 language | English (US) |
---|---|

Title of host publication | STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 634-643 |

Number of pages | 10 |

ISBN (Print) | 9781450327107 |

DOIs | |

State | Published - 2014 |

Event | 4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States Duration: May 31 2014 → Jun 3 2014 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | New York, NY |

Period | 5/31/14 → 6/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

*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