Document Open Access Logo

Satisfiability Thresholds for Regular Occupation Problems

Authors Konstantinos Panagiotou, Matija Pasch

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.90.pdf
  • Filesize: 488 kB
  • 14 pages

Document Identifiers

Author Details

Konstantinos Panagiotou
  • LMU München, Germany
Matija Pasch
  • LMU München, Germany

Funding

  • Panagiotou, Konstantinos: The research leading to these results has received funding from the European Research Council, ERC Grant Agreement 772606–PTRCSP.

Cite AsGet BibTex

Konstantinos Panagiotou and Matija Pasch. Satisfiability Thresholds for Regular Occupation Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 90:1-90:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.90

Abstract

In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. The two most popular types of such CSPs are the Erdős-Rényi and the random regular CSPs. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of problems of the latter type, the so-called occupation problems. The regular r-in-k occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the 1-in-k occupation problem has been rigorously established. In the present work we take a general approach towards a systematic analysis of occupation problems. In particular, we discover a surprising and explicit connection between the 2-in-k occupation problem satisfiability threshold and the determination of contraction coefficients, an important quantity in information theory measuring the loss of information that occurs when communicating through a noisy channel. We present methods to facilitate the computation of these coefficients and use them to establish explicitly the threshold for the 2-in-k occupation problem for k=4. Based on this result, for general k >= 5 we formulate a conjecture that pins down the exact value of the corresponding coefficient, which, if true, is shown to determine the threshold in all these cases.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Probability and statistics
  • Mathematics of computing → Probabilistic inference problems
  • Mathematics of computing → Probabilistic reasoning algorithms
  • Mathematics of computing → Information theory
Keywords
  • Constraint satisfaction problem
  • replica symmetric
  • contraction coefficient
  • first moment
  • second moment
  • small subgraph conditioning

Metrics

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

Related Versions

References

  1. E. Abbe. Community Detection and Stochastic Block Models: Recent Developments. Journal of Machine Learning Research, 18:1-86, 2018. Google Scholar
  2. R. Ahlswede, P. Gács, and J. Körner. Bounds on conditional probabilities with applications in multi-user communication. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 34(2):157-177, 1976. URL: http://dx.doi.org/10.1007/BF00535682.
  3. V. Anantharam, A. Gohari, S. Kamath, and C. Nair. On hypercontractivity and the mutual information between Boolean functions. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 13-19, October 2013. URL: http://dx.doi.org/10.1109/Allerton.2013.6736499.
  4. V. Anantharam, A. Gohari, S. Kamath, and C. Nair. On hypercontractivity and a data processing inequality. In 2014 IEEE International Symposium on Information Theory, pages 3022-3026, June 2014. URL: http://dx.doi.org/10.1109/ISIT.2014.6875389.
  5. H. Assiyatun and N. C. Wormald. 3-star factors in random d-regular graphs. European J. Combin., 27(8):1249-1262, 2006. URL: http://dx.doi.org/10.1016/j.ejc.2006.05.003.
  6. M. A. Bahmanian and M. Šajna. Quasi-Eulerian hypergraphs. Electron. J. Combin., 24(3):Paper 3.30, 12, 2017. Google Scholar
  7. V. Bapst, A. Coja-Oghlan, and C. Efthymiou. Planting colourings silently. Combin. Probab. Comput., 26(3):338-366, 2017. URL: http://dx.doi.org/10.1017/S0963548316000390.
  8. B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin., 1(4):311-316, 1980. URL: http://dx.doi.org/10.1016/S0195-6698(80)80030-8.
  9. A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Random Structures Algorithms, 27(2):201-226, 2005. URL: http://dx.doi.org/10.1002/rsa.20057.
  10. T. Castellani, V. Napolano, F. Ricci-Tersenghi, and R. Zecchina. Bicolouring random hypergraphs. J. Phys. A, 36(43):11037-11053, 2003. URL: http://dx.doi.org/10.1088/0305-4470/36/43/026.
  11. A. Coja-Oghla, T. Kapetanopoulos, and N. Müller. The replica symmetric phase of random constraint satisfaction problems. arXiv e-prints, page arXiv:1802.09311, February 2018. URL: http://arxiv.org/abs/1802.09311.
  12. A. Coja-Oghlan. Constraint satisfaction: random regular k-SAT. In Statistical physics, optimization, inference, and message-passing algorithms, pages 231-251. Oxford Univ. Press, Oxford, 2016. Google Scholar
  13. A. Coja-Oghlan, C. Efthymiou, N. Jaafari, M. Kang, and T. Kapetanopoulos. Charting the replica symmetric phase. Comm. Math. Phys., 359(2):603-698, 2018. URL: http://dx.doi.org/10.1007/s00220-018-3096-x.
  14. A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zdeborova. Information-theoretic thresholds from the cavity method. Adv. Math., 333:694-795, 2018. Google Scholar
  15. A. Coja-Oghlan and K. Panagiotou. The asymptotic k-SAT threshold. Adv. Math., 288:985-1068, 2016. URL: http://dx.doi.org/10.1016/j.aim.2015.11.007.
  16. C. Cooper, A. Frieze, M. Molloy, and B. Reed. Perfect matchings in random r-regular, s-uniform hypergraphs. Combin. Probab. Comput., 5(1):1-14, 1996. URL: http://dx.doi.org/10.1017/S0963548300001796.
  17. I. Csiszár and J. Körner. Information theory: coding theorems for discrete memoryless systems. Probability and mathematical statistics. Academic Press, 1981. URL: https://books.google.de/books?id=wiTvAAAAMAAJ.
  18. L. Dall'Asta, A. Ramezanpour, and R. Zecchina. Entropy landscape and non-Gibbs solutions in constraint satisfaction problems. Phys. Rev. E (3), 77(3):031118, 16, 2008. URL: http://dx.doi.org/10.1103/PhysRevE.77.031118.
  19. J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. In STOC'15 - Proceedings of the 2015 ACM Symposium on Theory of Computing, pages 59-68. ACM, New York, 2015. Google Scholar
  20. J. Ding, A. Sly, and N. Sun. Maximum independent sets on random regular graphs. Acta Math., 217(2):263-340, 2016. URL: http://dx.doi.org/10.1007/s11511-017-0145-9.
  21. J. Ding, A. Sly, and N. Sun. Satisfiability threshold for random regular NAE-SAT. Comm. Math. Phys., 341(2):435-489, 2016. URL: http://dx.doi.org/10.1007/s00220-015-2492-8.
  22. P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17-61, 1960. Google Scholar
  23. P. Erdős and A. Rényi. On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar., 17:359-368, 1966. URL: http://dx.doi.org/10.1007/BF01894879.
  24. U. Feige. Relations Between Average Case Complexity and Approximation Complexity. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 534-543, New York, NY, USA, 2002. ACM. Google Scholar
  25. A. Frieze, M. Jerrum, M. Molloy, R. W. Robinson, and N. C. Wormald. Generating and counting Hamilton cycles in random regular graphs. J. Algorithms, 21(1):176-198, 1996. URL: http://dx.doi.org/10.1006/jagm.1996.0042.
  26. M. Gabrié, V. Dani, G. Semerjian, and L. Zdeborová. Phase transitions in the q-coloring of random hypergraphs. J. Phys. A, 50(50):505002, 44, 2017. URL: http://dx.doi.org/10.1088/1751-8121/aa9529.
  27. A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-uniqueness Region. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 823-831, New York, NY, USA, 2014. Google Scholar
  28. R. G. Gallager. Information theory and reliable communication. Wiley, 1968. Google Scholar
  29. S. Higuchi and M. Mézard. Correlation-based decimation in constraint satisfaction problems. Journal of Physics: Conference Series, 233(1):012003, 2010. URL: http://stacks.iop.org/1742-6596/233/i=1/a=012003.
  30. S. Janson. Random regular graphs: asymptotic distributions and contiguity. Combin. Probab. Comput., 4(4):369-405, 1995. URL: http://dx.doi.org/10.1017/S0963548300001735.
  31. S. Janson, T. Łuczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. URL: http://dx.doi.org/10.1002/9781118032718.
  32. G. Kemkes, X. Pérez-Giménez, and N. C. Wormald. On the chromatic number of random d-regular graphs. Adv. Math., 223(1):300-328, 2010. URL: http://dx.doi.org/10.1016/j.aim.2009.08.006.
  33. F. Krzakala, F. Ricci-Tersenghi, L. Zdeborová, R. Zecchina, E. W. Tramel, and L. F. Cugliandolo, editors. Statistical physics, optimization, inference, and message-passing algorithms. Oxford University Press, Oxford, 2016. Google Scholar
  34. S. Kudekar, T. Richardson, and R. Urbanke. Spatially coupled ensembles universally achieve capacity under belief propagation. IEEE Trans. Inform. Theory, 59:7761-7813, 2013. Google Scholar
  35. E. Maneva, E. Mossel, and M. J. Wainwright. A new look at survey propagation and its generalizations. J. ACM, 54(4):Art. 17, 41, 2007. URL: http://dx.doi.org/10.1145/1255443.1255445.
  36. M. Mézard and A. Montanari. Information, physics, and computation. Oxford Graduate Texts. Oxford University Press, Oxford, 2009. URL: http://dx.doi.org/10.1093/acprof:oso/9780198570837.001.0001.
  37. M. Mézard, G. Parisi, and M. A. Virasoro. Spin glass theory and beyond, volume 9 of World Scientific Lecture Notes in Physics. World Scientific Publishing Co., Inc., Teaneck, NJ, 1987. Google Scholar
  38. M. Molloy, H. D. Robalewska, R. W. Robinson, and N. C. Wormald. 1-factorizations of random regular graphs. Random Structures Algorithms, 10(3):305-321, 1997. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#.
  39. C. Moore. The phase transition in random regular exact cover. Ann. Inst. Henri Poincaré D, 3(3):349-362, 2016. URL: http://dx.doi.org/10.4171/AIHPD/31.
  40. T. Mora. Geometry and Inference in Optimization and in Information Theory. Theses, Université Paris Sud - Paris XI, September 2007. URL: https://tel.archives-ouvertes.fr/tel-00175221.
  41. H. D. Robalewska. 2-factors in random regular graphs. J. Graph Theory, 23(3):215-224, 1996. URL: http://dx.doi.org/10.1002/(SICI)1097-0118(199611)23:3<215::AID-JGT1>3.3.CO;2-K.
  42. C. Schmidt, N. Guenther, and L. Zdeborová. Circular coloring of random graphs: statistical physics investigation. J. Stat. Mech. Theory Exp., 2016(8):083303, 28, 2016. URL: http://dx.doi.org/10.1088/1742-5468/2016/08/083303.
  43. M. Talagrand. Spin glasses: a challenge for mathematicians, volume 46 of Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics. Springer-Verlag, Berlin, 2003. Google Scholar
  44. N. C. Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239-298. Cambridge Univ. Press, Cambridge, 1999. Google Scholar
  45. L. Zdeborová and F. Krzakala. Quiet planting in the locked constraint satisfaction problems. SIAM J. Discrete Math., 25(2):750-770, 2011. URL: http://dx.doi.org/10.1137/090750755.
  46. L. Zdeborová and M. Mézard. Constraint satisfaction problems with isolated solutions are hard. J. Stat. Mech. Theory Exp., 2008(12):P12004, 2008. URL: http://stacks.iop.org/1742-5468/2008/i=12/a=P12004.
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 Imprint Privacy Contact