The number of satisfying assignments of random 2‐SAT formulas
From MaRDI portal
Publication:6074640
DOI10.1002/RSA.20993zbMATH Open1522.68375MaRDI QIDQ6074640FDOQ6074640
Authors:
Publication date: 12 October 2023
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Recommendations
Central limit and other weak theorems (60F05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)
Cites Work
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- The Complexity of Enumeration and Reliability Problems
- The probabilistic method
- Component behavior near the critical point of the random graph process
- The Monge-Kantorovich problem: achievements, connections, and perspectives
- Ising models on locally tree-like graphs
- Bounds for diluted mean-fields spin glass models
- Replica bounds for optimization problems and diluted spin systems
- Broken replica symmetry bounds in the mean field spin glass model
- Spin glass models from the point of view of spin distributions
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Title not available (Why is that?)
- Information, Physics, and Computation
- On the concentration of the number of solutions of random satisfiability formulas
- Proof of the satisfiability conjecture for large \(k\)
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- The Evolution of Random Graphs
- Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
- The satisfiability threshold for \(k\)-XORSAT
- Title not available (Why is that?)
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- The 3-XORSAT threshold.
- The scaling window of the 2-SAT transition
- Random 2-SAT: Results and problems
- A threshold for unsatisfiability
- Random MAX SAT, random MAX CUT, and their phase transitions
- Combinatorics and complexity of partition functions
- Factor models on locally tree-like graphs
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- The replica symmetric phase of random constraint satisfaction problems
- On the replica symmetric solution of the \(K\)-sat model
- The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
- Entropy of theK-Satisfiability Problem
- Length of prime implicants and number of solutions of random CNF formulae
- The asymptotic \(k\)-SAT threshold
- Counting good truth assignments of random \(k\)-SAT formulae
- Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
- The number of satisfying assignments of random regular \(k\)-SAT formulas
- Satisfiability threshold for random regular \textsc{nae-sat}
- The satisfiability threshold for random linear equations
- The high temperature case for the random \(K\)-sat problem
- Random 2-SAT with prescribed literal degrees
- On the number of solutions in random graph \(k\)-colouring
Cited In (12)
- Counting good truth assignments of random \(k\)-SAT formulae
- Tricritical points in random combinatorics: the -SAT case
- Exact enumeration of satisfiable 2-SAT formulae
- Random 2-SAT solution components and a fitness landscape
- On the number of 2-SAT functions
- Approximating highly satisfiable random 2-SAT
- Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity
- Random 2-SAT: Results and problems
- The number of satisfying assignments of random regular \(k\)-SAT formulas
- The structure of the set of satisfying assignments for a random \(k\)-CNF
- Counting solutions to random CNF formulas
- Belief propagation on the random \(k\)-SAT model
This page was built for publication: The number of satisfying assignments of random 2‐SAT formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074640)
