TY - GEN

T1 - Covering CSPs

AU - Dinur, Irit

AU - Kol, Gillat

PY - 2013

Y1 - 2013

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

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

KW - Covering Number

KW - PCP

KW - Unique Games Conjecture

UR - http://www.scopus.com/inward/record.url?scp=84885625829&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885625829&partnerID=8YFLogxK

U2 - 10.1109/CCC.2013.29

DO - 10.1109/CCC.2013.29

M3 - Conference contribution

AN - SCOPUS:84885625829

SN - 9780769549972

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 207

EP - 218

BT - Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013

T2 - 2013 IEEE Conference on Computational Complexity, CCC 2013

Y2 - 5 June 2013 through 7 June 2013

ER -