Document Open Access Logo

The Condensation Phase Transition in the Regular k-SAT Model

Authors Victor Bapst, Amin Coja-Oghlan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.22.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Victor Bapst
Amin Coja-Oghlan

Cite As Get BibTex

Victor Bapst and Amin Coja-Oghlan. The Condensation Phase Transition in the Regular k-SAT Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.22

Abstract

Much of the recent work on phase transitions in discrete structures has been inspired by ingenious but non-rigorous approaches from physics. The physics predictions typically come in the form of distributional fixed point problems that mimic Belief Propagation, a message passing algorithm. In this paper we show how the Belief Propagation calculation can be turned into a rigorous proof of such a prediction, namely the existence and location of a condensation phase transition in the regular k-SAT model.

Subject Classification

Keywords
  • random k-SAT
  • phase transitions
  • Belief Propagation
  • condensation

Metrics

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

References

  1. D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. In Proc. 49th FOCS, pages 793-802, 2008. Google Scholar
  2. D. Achlioptas and C. Moore. Random k-sat: two moments suffice to cross a sharp threshold. SIAM Journal on Computing, 36:740-762, 2006. Google Scholar
  3. D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435:759-764, 2005. Google Scholar
  4. D. Achlioptas and Y. Peres. The threshold for random k-sat is 2^k ln 2 - o(k). Journal of the AMS, 17:947-973, 2004. Google Scholar
  5. J. Banks and C. Moore. Information-theoretic thresholds for community detection in sparse networks. Information-theoretic thresholds for community detection in sparse networks, arXiv:1601.02658, 2016. Google Scholar
  6. V. Bapst and A. Coja-Oghlan. Harnessing the bethe free energy. Harnessing the Bethe free energy, arXiv:1504.03975, 2015. Google Scholar
  7. V. Bapst, A. Coja-Oghlan, S. Hetterich, F. Raßmann, and D. Vilenchik. The condensation phase transition in random graph coloring. Communications in Mathematical Physics, 341:543-606, 2016. Google Scholar
  8. V. Bapst, A. Coja-Oghlan, and F. Raßmann. A positive temperature phase transition in random hypergraph 2-coloring. Annals of Applied Probability, 26:1362?1406, 2016. Google Scholar
  9. B. Barak. Structure vs. combinatorics in computational complexity, 2013. Google Scholar
  10. M. Bayati, D. Gamarnik, and P. Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Annals of Probability, 41:4080-4115, 2013. Google Scholar
  11. A. Coja-Oghlan and K. Panagiotou. Going after the k-sat threshold. In Proc. 45th STOC, pages 705-714, 2013. Google Scholar
  12. A. Coja-Oghlan and K. Panagiotou. The asymptotic k-sat threshold. Advances in Mathematics, 288:985-1068, 2016. Google Scholar
  13. A. Coja-Oghlan and L. Zdeborová. The condensation transition in random hypergraph 2-coloring. In Proc. 23rd SODA, pages 241-250, 2012. Google Scholar
  14. P. Contucci, S. Dommers, C. Giardina, and S. Starr. Antiferromagnetic potts model on the Erdős-Rényi random graph. Communications in Mathematical Physics, 323:517-554, 2013. Google Scholar
  15. A. Dembo, A. Montanari, A. Sly, and N. Sun. The replica symmetric solution for potts models on d-regular graphs. Comm. Math. Phys., 327:551-575, 2014. Google Scholar
  16. J. Ding, A. Sly, and N. Sun. Maximum independent sets on random regular graphs. Maximum independent sets on random regular graphs, arXiv:1310.4787, 2013. Google Scholar
  17. J. Ding, A. Sly, and N. Sun. Satisfiability threshold for random regular nae-sat. In Proc. 46th STOC, pages 814-822, 2014. Google Scholar
  18. J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. In Proc. 47th STOC, pages 59-68, 2015. Google Scholar
  19. D. Gamarnik, T. Nowicki, and G. Swirszcz. Maximum weight independent sets and matchings in sparse random graphs: Exact results using the local weak convergence method. Random Structures and Algorithms, 28:76-106, 2006. Google Scholar
  20. D. Gamarnik and M. Sudan. Limits of local algorithms over sparse random graphs. In Proc. 5th ITCS, pages 369-376, 2014. Google Scholar
  21. D. Gamarnik and M. Sudan. Performance of the survey propagation-guided decimation algorithm for the random nae-k-sat problem. Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem, arXiv:1402.0052, 2014. Google Scholar
  22. F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborova. Gibbs states and and the set of solutions of random constraint satisfaction problems. Proc. National Academy of Sciences, 104:10318-10323, 2007. Google Scholar
  23. M. Mézard and A. Montanari. Information, physics and computation. Oxford University Press, 2009. Google Scholar
  24. M. Mézard, G. Parisi, and M. Virasoro. Spin Glass Theory and Beyond. World Scientific, 1987. Google Scholar
  25. M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297:812-815, 2002. Google Scholar
  26. E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, pages 1-31, 2014. Google Scholar
  27. D. Panchenko. On the replica symmetric solution of the k-sat model. Electron. J. Probab., 19:1-17, 2014. Google Scholar
  28. V. Rathi, E. Aurell, L. K. Rasmussen, and M. Skoglund. Bounds on threshold of regular random k-sat. In Proc. 12th SAT, pages 264-277, 2010. Google Scholar
  29. F. Ricci-Tersenghi and G. Semerjian. On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms. J. Stat. Mech., 9001, 2009. Google Scholar
  30. T. Richardson and R. Urbanke. Modern coding theory. Cambridge University Press, 2008. Google Scholar
  31. M. Talagrand. The high temperature case for the random k-sat problem. Probab. Theory Related Fields, 119:187-212, 2001. Google Scholar
  32. L. Zdeborová and F. Krzakala. Statistical physics of inference: Thresholds and algorithms. Statistical physics of inference: thresholds and algorithms, arXiv:1511.02476, 2015. 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