Counting Solutions to Random CNF Formulas

DOI10.1137/20M1351527zbMath1492.68062arXiv1911.07020OpenAlexW3194925747MaRDI QIDQ5096442

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

Publication date: 17 August 2022

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

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

zbMATH Keywords

satisfiabilityapproximate countingrandom \(k\)-SAT

Mathematics Subject Classification ID

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

Related Items (2)

Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth ⋮ Belief propagation on the random \(k\)-SAT model

Cites Work

• Unnamed Item
• The asymptotic \(k\)-SAT threshold
• Component structure in the evolution of random hypergraphs
• Asymptotic lower bounds for Ramsey functions
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Analyzing Walksat on Random Formulas
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the Satisfiability Conjecture for Large k
• The Number of Satisfying Assignments of Random Regulark-SAT Formulas
• Belief Propagation Guided Decimation Fails on Random Formulas
• A constructive proof of the general lovász local lemma
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• A parallel algorithmic version of the local lemma
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• Analysing Survey Propagation Guided Decimation on Random Formulas
• Sampling Random Colorings of Sparse Random Graphs
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Sampling in Potts Model on Sparse Random Graphs
• Fast sampling and counting 𝑘-SAT solutions in the local lemma regime
• Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
• Rapid mixing of hypergraph independent sets
• Counting Hypergraph Colorings in the Local Lemma Regime
• Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
• Uniform Sampling Through the Lovász Local Lemma
• Walksat Stalls Well Below Satisfiability
• A Better Algorithm for Random k-SAT
• New Constructive Aspects of the Lovász Local Lemma
• Deterministic Algorithms for the Lovász Local Lemma
• Probability and Computing
• A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• The number of satisfying assignments of random 2‐SAT formulas

This page was built for publication: Counting Solutions to Random CNF Formulas