Theory of Computing
-------------------
Title     : A Characterization of Hard-to-Cover CSPs
Authors   : Amey Bhangale, Prahladh Harsha, and Girish Varma
Volume    : 16
Number    : 16
Pages     : 1-30
URL       : https://theoryofcomputing.org/articles/v016a016

Abstract
--------

We continue the study of the _covering complexity_ of constraint
satisfaction problems (CSPs) initiated by Guruswami, Hastad 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:

  1. 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 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.

  2. For a large class of predicates that are contained in the
  2k-LIN predicate, we show that it is quasi-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 4-LIN covering hardness
  result of Dinur and Kol.