Document Open Access Logo

A Characterization of Hard-to-cover CSPs

Authors Amey Bhangale, Prahladh Harsha, Girish Varma

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.280.pdf
  • Filesize: 0.65 MB
  • 24 pages

Document Identifiers

Author Details

Amey Bhangale
Prahladh Harsha
Girish Varma

Cite As Get 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)))).

Subject Classification

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

  1. 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). Google Scholar
  2. 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). Google Scholar
  3. 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). Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. 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. Google Scholar
  7. Irit Dinur and Gillat Kol. Covering CSPs. In Proc. 28th IEEE Conf. on Computational Complexity, pages 207-218, 2013. Google Scholar
  8. 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. Google Scholar
  9. 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). Google Scholar
  10. 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. Google Scholar
  11. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, July 2001. (Preliminary version in 29th STOC, 1997). Google Scholar
  12. 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. Google Scholar
  13. 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. Google Scholar
  14. Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713-1756, 2010. (Preliminary version in 49th FOCS, 2008). Google Scholar
  15. Ran Raz. A parallel repetition theorem. SIAM J. Computing, 27(3):763-803, June 1998. (Preliminary version in 27th STOC, 1995). Google Scholar
  16. Girish Varma. A note on reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. (manuscript), 2014. Google Scholar
  17. 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). Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact