Volume 16 (2020)
Article 16 pp. 1-30

A Characterization of Hard-to-Cover CSPs

Received: October 13, 2016

Revised: September 10, 2018

Published: December 13, 2020

Revised: September 10, 2018

Published: December 13, 2020

**Keywords:**hardness of approximation, covering complexity, odd predicates

**ACM Classification:**F.2.2, F.1.3, G.1.6

**AMS Classification:**68Q25

**Abstract:**
[Plain Text Version]

$
\newcommand{\twoklin}{\mathsf{2k\text{-}LIN}}
\newcommand{\fourlin}{\mathsf{4\text{-}LIN}}
$

We continue the study of
the
*covering complexity* of constraint
satisfaction problems (CSPs) initiated by Guruswami, Håstad and
Sudan [SIAM J. Comp. 2002] and Dinur and Kol [CCC'13].
The covering number of a CSP instance
$\Phi$ is the smallest number of assignments
to the variables of $\Phi$, such that each constraint of $\Phi$ is
satisfied by at least one of the assignments. We show the following
results:

- Assuming a covering
variant of the
Unique Games Conjecture,
introduced by
Dinur and Kol, we show that for every non-odd predicate $P$ over
any constant-size alphabet and every integer $K$, it is
$\mathrm{NP}$-hard to approximate the covering number within a
factor of $K$. This yields a complete characterization of CSPs
over constant-size alphabets that are hard to cover.
- For a large class of predicates that are contained in the $\twoklin$ predicate, we show that it is quasi-$\mathrm{NP}$-hard to distinguish between instances with covering number at most $2$ and those with covering number at least $\Omega(\log\log n)$. This generalizes and improves the $\fourlin$ covering hardness result of Dinur and Kol.

---------------

A preliminary version of this paper appeared in the Proceedings of the 30th Computational Complexity Conference (CCC), 2015.