  We continue the study of the covering complexity of constraint satisfaction
problems (CSPs) initiated by Guruswami, H{\aa}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:
  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.
