Theory of Computing
-------------------
Title : From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
Authors : Mrinalkanti Ghosh and Madhur Tulsiani
Volume : 14
Number : 10
Pages : 1-33
URL : http://www.theoryofcomputing.org/articles/v014a010
Abstract
--------
We study the approximability of constraint satisfaction problems
(CSPs) by linear programming (LP) relaxations. We show that for every
CSP, the approximation obtained by a basic LP relaxation is at least
as strong as the approximation obtained using relaxations given by $c
\cdot \log n/\log \log n$ levels of the Sherali--Adams hierarchy (for
some constant $c > 0$) on instances of size $n$.
It was proved by Chan et al. [FOCS 2013] (and recently
strengthened by Kothari et al. [STOC 2017]) that for CSPs, any
polynomial-size LP extended formulation is at most as strong as the
relaxation obtained by a constant number of levels of the Sherali--
Adams hierarchy (where the number of levels depend on the exponent of
the polynomial in the size bound). Combining this with our result also
implies that any polynomial-size LP extended formulation is at most as
strong as the _basic_ LP, which can be thought of as the base level of
the Sherali--Adams hierarchy. This essentially gives a dichotomy
result for approximation of CSPs by polynomial-size LP extended
formulations.
Using our techniques, we also simplify and strengthen the
result by Khot et al. [STOC 2014] on (strong) approximation resistance
for LPs. They provided a necessary and sufficient condition under
which $\littleoh(\log \log n)$ levels of the Sherali--Adams hierarchy
cannot achieve an approximation better than a random assignment. We
simplify their proof and strengthen the bound to
$\littleoh\inparen{\log n/\log \log n}$ levels.
A conference version of this paper appeared in the Proceedings of
the 32nd Computational Complexity Conference (CCC'17).