The Long, the Short and the Random
This addresses a fundamental computational challenge in theoretical computer science, specifically for SAT problems, but appears incremental as it builds on known combinatorial properties.
The authors tackled the problem of exactly counting satisfying assignments for random sparse #Ω(log n)-SAT instances, and they presented a deterministic algorithm that achieves sub-exponential time complexity, supported by theoretical and empirical evidence.
We furnish solid evidence, both theoretical and empirical, towards the existence of a deterministic algorithm for random sparse $\#Ω(\log n)$-SAT instances, which computes the exact counting of satisfying assignments in sub-exponential time. The algorithm uses a nice combinatorial property that every CNF formula has, which relates its number of unsatisfying assignments to the space of its monotone sub-formulae.