Projects per year
We give the first eﬀicient 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.
|Number of pages||38|
|Journal||SIAM Journal on Computing|
|Publication status||Published - 29 Nov 2021|
- random k-SAT
- approximate counting
FingerprintDive into the research topics of 'Counting Solutions to Random CNF Formulas'. Together they form a unique fingerprint.
- 1 Active
New Approaches to Counting and Sampling
1/01/21 → 31/12/25