Covering CSPs

Irit Dinur, Gillat Kol

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted v(C), is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we must satisfy all the constraints, and are willing to use more than one assignment to do so. At the same time, we want to minimize the number of assignments. We study the covering problem for different constraint predicates. We first observe that if the predicate contains an odd predicate, then it is covered by any assignment and its negation. In particular, 3CNF and 3LIN, that are hard in the max-CSP sense, are easy to cover. However, the covering problem is hard for predicates that do not contain an odd predicate: 1. For the 4LIN predicate, it is NP-hard to decide if a given instance C has v(C) at most 2, or v(C) is super-constant. 2. (a) We propose a framework of covering dictatorship tests. We design and analyze such a dictatorship test for every predicate that supports a pair wise independent distribution. (b) We introduce a covering unique games conjecture, and use it to convert the covering dictatorship tests into conditional hardness results. 3. Finally, we study a hypothesis about the hardness of covering random instances that is similar to Feige's R3SAT hypothesis. We show the following somewhat surprising implication: If our hypothesis holds for dense enough instances, then it is hard to color an O(1)-colorable hyper graph with a polynomial number of colors.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013
Number of pages12
StatePublished - 2013
Externally publishedYes
Event2013 IEEE Conference on Computational Complexity, CCC 2013 - Palo Alto, CA, United States
Duration: Jun 5 2013Jun 7 2013

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159


Other2013 IEEE Conference on Computational Complexity, CCC 2013
Country/TerritoryUnited States
CityPalo Alto, CA

All Science Journal Classification (ASJC) codes

  • Software
  • Computational Mathematics
  • Theoretical Computer Science


  • Covering Number
  • PCP
  • Unique Games Conjecture


Dive into the research topics of 'Covering CSPs'. Together they form a unique fingerprint.

Cite this