The number of satisfying assignments of random regular k-SAT formulas

DOI10.1017/S0963548318000263MaRDI QIDQ3177360zbMATH OpenFDO

Authors Amin Coja-Oghlan, Nicholas Wormald

Publication date 24 July 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: Let $Phi$ be a random $k$-SAT formula in which every variable occurs precisely $d$ times positively and $d$ times negatively. Assuming that $k$ is sufficiently large and that $d$ is slightly below the critical degree where the formula becomes unsatisfiable with high probability, we determine the limiting distribution of the logarithm of the number of satisfying assignments.

Recommendations

• Constraint satisfaction: random regular k-SAT
• The number of satisfying assignments of random 2‐SAT formulas
• On the maximum satisfiability of random formulas
• On the concentration of the number of solutions of random satisfiability formulas
• The asymptotic k-SAT threshold

Cites work

• scientific article; zbMATH DE number 1033851 (Why is no real title available?)
• scientific article; zbMATH DE number 3435482 (Why is no real title available?)
• Almost all cubic graphs are Hamiltonian
• An elementary proof of the local central limit theorem
• An estimate of the remainder in a combinatorial central limit theorem
• Approximating the unsatisfiability threshold of random formulas
• Bounds on threshold of regular random k-SAT
• Going after the k-SAT threshold
• On the number of solutions in random hypergraph 2-colouring
• Paths in graphs
• Proof of the satisfiability conjecture for large k
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Random k-SAT: A tight threshold for moderately growing k
• Satisfiability threshold for random regular NAE-SAT
• The asymptotic k-SAT threshold
• The condensation phase transition in the regular $k$-SAT model
• The condensation transition in random hypergraph 2-coloring
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

Cited in

(20)

• On the concentration of the number of solutions of random satisfiability formulas
• Solving non-uniform planted and filtered random SAT formulas greedily
• Geometric properties of satisfying assignments of random ε-1-in-kSAT
• Charting the replica symmetric phase
• The replica symmetric phase of random constraint satisfaction problems
• Constraint satisfaction: random regular k-SAT
• On the number of solutions in random hypergraph 2-colouring
• Counting solutions to random CNF formulas
• Random k-sat: the limiting probability for satisfiability for moderately growing k
• 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
• A general framework for hypergraph coloring
• Regular random \(k\)-SAT: Properties of balanced formulas
• The number of random 2-SAT solutions is asymptotically log-normal
• The number of satisfying assignments of random 2‐SAT formulas
• The structure of the set of satisfying assignments for a random \(k\)-CNF
• Counting solutions to random CNF formulas
• One-step replica symmetry breaking of random regular NAE-SAT. II
• scientific article; zbMATH DE number 7561554 (Why is no real title available?)
• Belief propagation on the random \(k\)-SAT model

This page was built for publication: The number of satisfying assignments of random regular \(k\)-SAT formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177360)