Volume 13 (2017) Article 3 pp. 1-24
APPROX-RANDOM 2015 Special Issue
Towards a Characterization of Approximation Resistance for Symmetric CSPs
Received: December 26, 2015
Revised: August 7, 2016
Published: June 13, 2017
Download article from ToC site:
[PDF (345K)]    [PS (1680K)]    [PS.GZ (414K)]
[Source ZIP]
Keywords: inapproximability, UG-hardness, constraint satisfaction, semidefinite programming
ACM Classification: F.2.2 (Nonnumerical Algorithms and Problems)
AMS Classification: 68W25 (Approximation algorithms)

Abstract: [Plain Text Version]

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to $1$ with some probability $\alpha$ achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), where satisfaction of each constraint only depends on the number of true literals in its scope. Thus a SCSP of arity $k$ can be described by a subset $S \subseteq \{0,1,\dots,k\}$ of allowed number of true literals.

For SCSPs without negation, we conjecture that a simple sufficient condition to be approximation resistant by Austrin and Håstad is indeed necessary. We show that this condition has a compact analytic representation in the case of symmetric CSPs (depending only on the gap between the largest and smallest numbers in $S$), and provide the rationale behind our conjecture. We prove two interesting special cases of the conjecture, (i) when $S$ is an interval (i.e., $S = \{ i \mid \ell \le i \le r\}$ for some $\ell \le r$) and (ii) when $S$ is even (i.e., $s \in S \Leftrightarrow k-s \in S$). For SCSPs with negation, we prove that the analogous sufficient condition by Austrin and Mossel is necessary for the same two cases, though we do not pose an analogous conjecture in general.

A conference version of this paper appeared in the Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2015 (APPROX'15).