A Characterization of Hard-to-cover CSPs

Bhangale, Amey; Harsha, Prahladh; Varma, Girish

doi:10.4230/LIPIcs.CCC.2015.280

File

LIPIcs.CCC.2015.280.pdf

Filesize: 0.65 MB
24 pages

Document Identifiers

DOI: 10.4230/LIPIcs.CCC.2015.280
URN: urn:nbn:de:0030-drops-50574

Author Details

Amey Bhangale

Prahladh Harsha

Girish Varma

Cite AsGet BibTex

Amey Bhangale, Prahladh Harsha, and Girish Varma. A Characterization of Hard-to-cover CSPs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 280-303, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CCC.2015.280

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):1663--1686, 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 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 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 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 Omega(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 Omega(log(log(log(n)))).

Keywords

CSPs
Covering Problem
Hardness of Approximation
Unique Games
Invariance Principle

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, May 1998. (Preliminary version in 33rd FOCS, 1992).
Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, January 1998. (Preliminary version in 33rd FOCS, 1992).
Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249-271, 2009. (Preliminary version in 23rd IEEE Conference on Computational Complexity, 2008).
Nikhil Bansal and Subhash Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Proc. 37th International Colloq. of Automata, Languages and Programming (ICALP), Part I, volume 6198 of LNCS, pages 250-261. Springer, 2010.
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer. Making the long code shorter. In Proc. 53rd IEEE Symp. on Foundations of Comp. Science (FOCS), pages 370-379, 2012.
Irit Dinur and Venkatesan Guruswami. PCPs via low-degree long code and hardness for constrained hypergraph coloring. In Proc. 54th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 340-349, 2013.
Irit Dinur and Gillat Kol. Covering CSPs. In Proc. 28th IEEE Conf. on Computational Complexity, pages 207-218, 2013.
Venkat Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, and Girish Varma. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. In Proc. 46th ACM Symp. on Theory of Computing (STOC), pages 614-623, 2014.
Venkatesan Guruswami, Johan Håstad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM J. Computing, 31(6):1663-1686, 2002. (Preliminary Version in 41st FOCS, 2000).
Venkatesan Guruswami and Euiwoong Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. In Proc. 26th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 822-836, 2015.
Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, July 2001. (Preliminary version in 29th STOC, 1997).
Subhash Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proc. 43rd IEEE Symp. on Foundations of Comp. Science (FOCS), pages 23-32, 2002.
Subhash Khot and Rishi Saket. Hardness of coloring 2-colorable 12-uniform hypergraphs with 2^(log n)^Ω(1) colors. In Proc. 55th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 206-215, 2014.
Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713-1756, 2010. (Preliminary version in 49th FOCS, 2008).
Ran Raz. A parallel repetition theorem. SIAM J. Computing, 27(3):763-803, June 1998. (Preliminary version in 27th STOC, 1995).
Girish Varma. A note on reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. (manuscript), 2014.
Cenny Wenner. Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theory Comput., 9(23):703-757, 2013. (Preliminary version in APPROX, 2012).