Document Open Access Logo

Counting Solutions to Random CNF Formulas

Authors Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.53.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Galanis
  • Department of Computer Science, University of Oxford, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, UK
Heng Guo
  • School of informatics, University of Edinburgh, UK
Kuan Yang
  • Department of Computer Science, University of Oxford, UK

Funding

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 334828. The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

Cite AsGet BibTex

Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang. Counting Solutions to Random CNF Formulas. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.53

Abstract

We give the first efficient algorithm to approximately count the number of solutions in the random k-SAT model when the density of the formula scales exponentially with k. The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities (1+o_k(1))(2log k)/k, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas with much higher densities. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Randomness, geometry and discrete structures
  • Mathematics of computing → Discrete mathematics
Keywords
  • random CNF formulas
  • approximate counting

Metrics

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

Related Versions

  • A full version with all proofs is at https://arxiv.org/abs/1911.07020. The theorem numbers here match those in the full version. Proof sketches here refer to lemmas in the full version without restating them in detail.

References

  1. E. Abbe and A. Montanari. On the concentration of the number of solutions of random satisfiability formulas. Random Struct. Algorithms, 45(3):362-382, 2014. Google Scholar
  2. D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. In FOCS, pages 793-802. IEEE Computer Society, 2008. Google Scholar
  3. D. Achlioptas and C. Moore. The asymptotic order of the random k-SAT threshold. In FOCS, pages 779-788. IEEE Computer Society, 2002. Google Scholar
  4. D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2^k(ln 2 - o(k)). In STOC, pages 223-231. ACM, 2003. Google Scholar
  5. N. Alon. A parallel algorithmic version of the local lemma. Random Struct. Algorithms, 2(4):367-378, 1991. URL: https://doi.org/10.1002/rsa.3240020403.
  6. I. Bezáková, A. Galanis, L. A. Goldberg, H. Guo, and D. Štefankovič. Approximation via correlation decay when strong spatial mixing fails. SIAM J. Comput., 48(2):279-349, 2019. Google Scholar
  7. K. Chandrasekaran, N. Goyal, and B. Haeupler. Deterministic algorithms for the Lovász local lemma. SIAM J. Comput., 42(6):2132-2155, 2013. Google Scholar
  8. A. Coja-Oghlan. A better algorithm for random k-SAT. SIAM J. Comput., 39(7):2823-2864, 2010. Google Scholar
  9. A. Coja-Oghlan. Belief propagation guided decimation fails on random formulas. J. ACM, 63(6):Art. 49, 55, 2017. Google Scholar
  10. A. Coja-Oghlan and A. Frieze. Analyzing Walksat on random formulas. SIAM J. Comput., 43(4):1456-1485, 2014. Google Scholar
  11. A. Coja-Oghlan, A. Haqshenas, and S. Hetterich. Walksat stalls well below satisfiability. SIAM J. Discrete Math., 31(2):1160-1173, 2017. Google Scholar
  12. A. Coja-Oghlan and K. Panagiotou. The asymptotic k-SAT threshold. Adv. Math., 288:985-1068, 2016. Google Scholar
  13. A. Coja-Oghlan and D. Reichman. Sharp thresholds and the partition function. Journal of Physics: Conference Series, 473:012015, 2013. Google Scholar
  14. A. Coja-Oghlan and N. Wormald. The number of satisfying assignments of random regular k-SAT formulas. Combin. Probab. Comput., 27(4):496-530, 2018. Google Scholar
  15. J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. In STOC, pages 59-68. ACM, 2015. Google Scholar
  16. C. Efthymiou, T. P. Hayes, D. Štefankovič, and E. Vigoda. Sampling random colorings of sparse random graphs. In SODA, pages 1759-1771. SIAM, 2018. Google Scholar
  17. P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609-628, 1975. Google Scholar
  18. W. Feng, H. Guo, Y. Yin, and C. Zhang. Fast sampling and counting k-sat solutions in the local lemma regime, 2019. URL: http://arxiv.org/abs/1911.01319.
  19. E. Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):1017-1054, 1999. With an appendix by Jean Bourgain. URL: https://doi.org/10.1090/S0894-0347-99-00305-7.
  20. H. Guo, M. Jerrum, and J. Liu. Uniform sampling through the Lovász local lemma. J. ACM, 66(3):18:1-18:31, 2019. Google Scholar
  21. H. Guo, C. Liao, P. Lu, and C. Zhang. Counting hypergraph colorings in the local lemma regime. SIAM J. Comput., 48(4):1397-1424, 2019. Google Scholar
  22. B. Haeupler, B. Saha, and A. Srinivasan. New constructive aspects of the Lovász local lemma. J. ACM, 58(6):Art. 28, 28, 2011. Google Scholar
  23. J. Hermon, A. Sly, and Y. Zhang. Rapid mixing of hypergraph independent sets. Random Struct. Algorithms, 54(4):730-767, 2019. Google Scholar
  24. S. Hetterich. Analysing survey propagation guided decimationon random formulas. In ICALP, volume 55 of LIPIcs, pages 65:1-65:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  25. L. M. Kirousis, E. Kranakis, D. Krizanc, and Y. C. Stamatiou. Approximating the unsatisfiability threshold of random formulas. Random Structures Algorithms, 12(3):253-269, 1998. Google Scholar
  26. C. Liao, J. Lin, P. Lu, and Z. Mao. Counting independent sets and colorings on random regular bipartite graphs. In APPROX-RANDOM, volume 145 of LIPIcs, pages 34:1-34:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  27. M. Mézard, T. Mora, and R. Zecchina. Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett., 94:197205, 2005. Google Scholar
  28. M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812-815, 2002. Google Scholar
  29. M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Google Scholar
  30. A. Moitra. Approximate counting, the Lovász local lemma, and inference in graphical models. J. ACM, 66(2):Art. 10, 25, 2019. Google Scholar
  31. A. Montanari and D. Shah. Counting good truth assignments of random k-SAT formulae. In SODA, pages 1255-1264. SIAM, 2007. Google Scholar
  32. R. A. Moser and G. Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15, 2010. Google Scholar
  33. E. Mossel and A. Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab., 41(1):294-328, 2013. Google Scholar
  34. J. Schmidt-Pruzan and E. Shamir. Component structure in the evolution of random hypergraphs. Combinatorica, 5(1):81-94, 1985. Google Scholar
  35. A. Sly, N. Sun, and Y. Zhang. The number of solutions for random regular NAE-SAT. In FOCS, pages 724-731. IEEE Computer Society, 2016. Google Scholar
  36. J. Spencer. Asymptotic lower bounds for Ramsey functions. Discrete Math., 20(1):69-76, 1977. Google Scholar
  37. Y. Yin and C. Zhang. Sampling in Potts model on sparse random graphs. In APPROX-RANDOM, volume 60 of LIPIcs, pages 47:1-47:22. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. 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 Imprint Privacy Contact