Paper Info
Title
A Characterization of hard-to-cover CSPs.
Abstract
We continue the study of covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Håstad and Sudan [9] and Dinur and Kol [7]. The covering number of a CSP instance Φ, denoted by ν (Φ) is the smallest number of assignments to the variables of Φ, such that each constraint of Φ is satisfied by at least one of the assignments. We show the following results regarding how well efficient algorithms can approximate the covering number of a given CSP instance. 1. Assuming a covering unique games conjecture, introduced by Dinur and Kol, we show that for every non-odd predicate P over any constant sized alphabet and every integer K, it is NP-hard to distinguish between P-CSP instances (i.e., CSP instances where all the constraints are of type P) which are coverable by a constant number of assignments and those whose covering number is at least K. Previously, Dinur and Kol, using the same covering unique games conjecture, had shown a similar hardness result for every non-odd predicate over the Boolean alphabet that supports a pairwise independent distribution. Our generalization yields a complete characterization of CSPs over constant sized alphabet Σ that are hard to cover since CSPs over odd predicates are trivially coverable with |Σ| assignments. 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 which have covering number at most two and covering number at least Ω(log log n). This generalizes the 4-LIN result of Dinur and Kol that states it is quasi-NP-hard to distinguish between 4-LIN-CSP instances which have covering number at most two and covering number at least Ω(log log log n).
Year
DOI
Venue
2014
10.4230/LIPIcs.CCC.2015.280
CCC '15 Proceedings of the 30th Conference on Computational Complexity
Keywords
Field
DocType
CSPs,Covering Problem,Hardness of Approximation,Unique Games,Invariance Principle
Integer,Discrete mathematics,Binary logarithm,Combinatorics,Invariance principle,Unique games conjecture,Covering number,Hardness of approximation,Pairwise independence,Complexity of constraint satisfaction,Mathematics
Journal
Volume
ISSN
Citations 
abs/1411.7747
1868-8969
0
PageRank 
References 
Authors
0.34
14
3
Name
Order
Citations
PageRank
Amey Bhangale1106.71
Prahladh Harsha200.68
Girish Varma300.34