Counting solutions to random CNF formulas

DOI10.1137/20M1351527zbMATH Open1492.68062arXiv1911.07020OpenAlexW3194925747MaRDI QIDQ5096442FDOQ5096442

Authors: Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang 

Publication date: 17 August 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: 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 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+o_k(1))frac2logkk$, 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.

Full work available at URL: https://arxiv.org/abs/1911.07020

Recommendations

• Counting good truth assignments of random \(k\)-SAT formulae
• An approximation algorithm for \(\#k\)-SAT
• Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
• A Better Algorithm for Random k-SAT
• Solving and sampling with many solutions

zbMATH Keywords

approximate countingsatisfiabilityrandom \(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25) Combinatorial probability (60C05) Computational aspects of satisfiability (68R07)

Cites Work

• Probability and Computing
• Asymptotic lower bounds for Ramsey functions
• Approximating the unsatisfiability threshold of random formulas
• A constructive proof of the general Lovász local lemma
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the satisfiability conjecture for large \(k\)
• Sharp thresholds of graph properties, and the $k$-sat problem
• Component structure in the evolution of random hypergraphs
• Analyzing Walksat on random formulas
• Exact thresholds for Ising-Gibbs samplers on general graphs
• A parallel algorithmic version of the local lemma
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• New constructive aspects of the Lovász local lemma
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Deterministic algorithms for the Lovász local lemma
• A better algorithm for random \(k\)-SAT
• Sampling random colorings of sparse random graphs
• A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
• The asymptotic \(k\)-SAT threshold
• Counting good truth assignments of random \(k\)-SAT formulae
• The number of satisfying assignments of random regular \(k\)-SAT formulas
• Uniform sampling through the Lovász local lemma
• Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
• Walksat Stalls Well Below Satisfiability
• Belief propagation guided decimation fails on random formulas
• Analysing survey propagation guided decimationon random formulas
• Approximate counting, the Lovász local lemma, and inference in graphical models
• The number of satisfying assignments of random 2‐SAT formulas
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Rapid mixing of hypergraph independent sets
• Counting hypergraph colorings in the local lemma regime
• Sampling in Potts model on sparse random graphs
• Fast sampling and counting 𝑘-SAT solutions in the local lemma regime

Cited In (7)

• Counting good truth assignments of random \(k\)-SAT formulae
• Random CNF's are hard for the polynomial calculus
• 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
• Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
• Model counting of monotone conjunctive normal form formulas with spectra
• 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)