Correlation Decay and Tractability of CSPs

Authors Jonah Brown-Cohen, Prasad Raghavendra



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.79.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Jonah Brown-Cohen
Prasad Raghavendra

Cite AsGet BibTex

Jonah Brown-Cohen and Prasad Raghavendra. Correlation Decay and Tractability of CSPs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.79

Abstract

The algebraic dichotomy conjecture of Bulatov, Krokhin and Jeavons yields an elegant characterization of the complexity of constraint satisfaction problems. Roughly speaking, the characterization asserts that a CSP L is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to L to create new ones. In this work, we study the dynamical system associated with repeated applications of a polymorphism to a distribution over assignments. Specifically, we exhibit a correlation decay phenomenon that makes two variables or groups of variables that are not perfectly correlated become independent after repeated applications of a polymorphism. We show that this correlation decay phenomenon can be utilized in designing algorithms for CSPs by exhibiting two applications: 1. A simple randomized algorithm to solve linear equations over a prime field, whose analysis crucially relies on correlation decay. 2. A sufficient condition for the simple linear programming relaxation for a 2-CSP to be sound (have no integrality gap) on a given instance.
Keywords
  • Constraint Satisfaction
  • Polymorphisms
  • Linear Equations
  • Correlation Decay

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. In FOCS, pages 595-603, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.32.
  2. Libor Barto and Marcin Kozik. Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Logical Methods in Computer Science, 8(1), 2012. URL: http://dx.doi.org/10.2168/LMCS-8(1:7)2012.
  3. Andrei A. Bulatov. Tractable conservative constraint satisfaction problems. In LICS, pages 321-330, 2003. URL: http://dx.doi.org/10.1109/LICS.2003.1210072.
  4. Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006. URL: http://dx.doi.org/10.1145/1120582.1120584.
  5. Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for mal'tsev constraints. SIAM J. Comput., 36(1):16-27, 2006. URL: http://dx.doi.org/10.1137/050628957.
  6. Andrei A. Bulatov, Andrei A. Krokhin, and Peter Jeavons. Constraint satisfaction problems and finite algebras. In ICALP, pages 272-282, 2000. URL: http://dx.doi.org/10.1007/3-540-45022-X_24.
  7. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. URL: http://dx.doi.org/10.1137/S0097539794266766.
  8. Gábor Kun and Mario Szegedy. A new line of attack on the dichotomy conjecture. In STOC, pages 725-734, 2009. URL: http://dx.doi.org/10.1145/1536414.1536512.
  9. Miklós Maróti and Ralph McKenzie. Existence theorems for weakly symmetric operations. Algebra Universalis, 59:463-489, 2008. URL: http://dx.doi.org/10.1007/s00012-008-2122-9.
  10. E. Mossel. Gaussian bounds for noise correlation of functions. In FOCS'08: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008. Google Scholar
  11. Thomas J. Schaefer. The complexity of satisfiability problems. In STOC, pages 216-226, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
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