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

DOI10.1017/S0963548318000263MaRDI QIDQ3177360zbMATHFDO

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

(18)

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

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)