Counting solutions to random CNF formulas
From MaRDI portal
Publication:5096442
Abstract: We give the first efficient algorithm to approximately count the number of solutions in the random -SAT model when the density of the formula scales exponentially with . 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 , the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. 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.
Recommendations
Cites work
- A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
- A better algorithm for random \(k\)-SAT
- A constructive proof of the general Lovász local lemma
- A parallel algorithmic version of the local lemma
- Analysing survey propagation guided decimationon random formulas
- Analyzing Walksat on random formulas
- Approximate counting, the Lovász local lemma, and inference in graphical models
- Approximating the unsatisfiability threshold of random formulas
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- Asymptotic lower bounds for Ramsey functions
- Belief propagation guided decimation fails on random formulas
- Component structure in the evolution of random hypergraphs
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
- Counting good truth assignments of random \(k\)-SAT formulae
- Counting hypergraph colorings in the local lemma regime
- Deterministic algorithms for the Lovász local lemma
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Fast sampling and counting 𝑘-SAT solutions in the local lemma regime
- New constructive aspects of the Lovász local lemma
- On the concentration of the number of solutions of random satisfiability formulas
- Probability and Computing
- Proof of the satisfiability conjecture for large \(k\)
- Rapid mixing of hypergraph independent sets
- Sampling in Potts model on sparse random graphs
- Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
- Sampling random colorings of sparse random graphs
- Sharp thresholds of graph properties, and the $k$-sat problem
- The asymptotic \(k\)-SAT threshold
- The number of satisfying assignments of random 2‐SAT formulas
- The number of satisfying assignments of random regular \(k\)-SAT formulas
- The threshold for random k-SAT is 2 k (ln 2 - O(k))
- Uniform sampling through the Lovász local lemma
- Walksat Stalls Well Below Satisfiability
Cited in
(8)- Model counting of monotone conjunctive normal form formulas with spectra
- Rényi entropies as a measure of the complexity of counting problems
- Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
- Counting good truth assignments of random \(k\)-SAT formulae
- Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth
- Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity
- Random CNF's are hard for the polynomial calculus
- Belief propagation on the random \(k\)-SAT model
This page was built for publication: Counting solutions to random CNF formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096442)
