Counting solutions to random CNF formulas

Andreas Galanis, Leslie Ann Goldberg, Heng Guo +1

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…