The Number of Satisfying Assignments of Random Regular k-SAT Formulas

Amin Coja-Oghlan, Nick Wormald

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

Let Φ be a random k-SAT formula in which every variable occurs precisely d times positively and d times negatively. Assuming that k is sufficiently large and that d is slightly below the critical degree where the formula becomes unsatisfiable with high probability, we determine the limiting distribution of the number of satisfying assignments.

Original languageEnglish
Pages (from-to)496-530
Number of pages35
JournalCombinatorics Probability and Computing
Volume27
Issue number4
DOIs
Publication statusPublished - 1 Jul 2018

Cite this