Counting Solutions to Random CNF Formulas

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We give the first efficient algorithm to approximately count the number of solutions in the randomk-SAT model when the density of the formula scales exponentially with k.The best previous counting algorithm for the permissive version of the model was due to Montanari and Shah and was based on the correlation decay method, which works up to densities (1+ok(1))2logk/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.
Original languageEnglish
Pages (from-to)1701-1738
Number of pages38
JournalSIAM Journal on Computing
Issue number6
Publication statusPublished - 29 Nov 2021


  • random k-SAT
  • approximate counting
  • satisfiability


Dive into the research topics of 'Counting Solutions to Random CNF Formulas'. Together they form a unique fingerprint.

Cite this