Theory of Computing
-------------------
Title     : Towards a Characterization of Approximation Resistance for Symmetric CSPs
Authors   : Venkatesan Guruswami and Euiwoong Lee
Volume    : 13
Number    : 3
Pages     : 1-24
URL       : https://theoryofcomputing.org/articles/v013a003

Abstract
--------

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 Hastad 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 l \le i \le r\}$ for some $l \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).