Bhangale, Amey ;
Harsha, Prahladh ;
Varma, Girish
A Characterization of Hardtocover CSPs
Abstract
We continue the study of covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Håstad and Sudan [SIAM J. Computing, 31(6):16631686, 2002] and Dinur and Kol [in Proc. 28th IEEE Conference on Computational Complexity, 2013]. The covering number of a CSP instance Phi, denoted by nu(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 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 nonodd predicate P over any constant sized alphabet and every integer K, it is NPhard to distinguish between PCSP 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 nonodd predicate over the Boolean alphabet that supports a pairwise independent distribution. Our generalization yields a complete characterization of CSPs over constant sized alphabet Sigma that are hard to cover since CSPs over odd predicates are trivially coverable with Sigma assignments.
2. For a large class of predicates that are contained in the 2kLIN predicate, we show that it is quasiNPhard to distinguish between instances which have covering number at most two and covering number at least Omega(log(log(n))). This generalizes the 4LIN result of Dinur and Kol that states it is quasiNPhard to distinguish between 4LINCSP instances which have covering number at most two and covering number at least Omega(log(log(log(n)))).
BibTeX  Entry
@InProceedings{bhangale_et_al:LIPIcs:2015:5057,
author = {Amey Bhangale and Prahladh Harsha and Girish Varma},
title = {{A Characterization of Hardtocover CSPs}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {280303},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5057},
URN = {urn:nbn:de:0030drops50574},
doi = {10.4230/LIPIcs.CCC.2015.280},
annote = {Keywords: CSPs, Covering Problem, Hardness of Approximation, Unique Games, Invariance Principle}
}
06.06.2015
Keywords: 

CSPs, Covering Problem, Hardness of Approximation, Unique Games, Invariance Principle 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

06.06.2015 