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

DOI10.1017/S0963548318000263zbMATH Open1393.60010arXiv1611.03236MaRDI QIDQ3177360FDOQ3177360

Nicholas Wormald, Amin Coja-Oghlan

Publication date: 24 July 2018

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• Geometric properties of satisfying assignments of random ε-1-in-kSAT
• Solving non-uniform planted and filtered random SAT formulas greedily
• A General Framework for Hypergraph Coloring
• Charting the replica symmetric phase
• The replica symmetric phase of random constraint satisfaction problems
• On the number of solutions in random hypergraph 2-colouring
• Counting Solutions to Random CNF Formulas
• 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 \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
• The number of satisfying assignments of random 2‐SAT formulas
• The structure of the set of satisfying assignments for a random \(k\)-CNF
• One-step replica symmetry breaking of random regular NAE-SAT. II
• Title not available (Why is that?)
• 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)