Approximating the unsatisfiability threshold of random formulas

Recommendations

Approximating the unsatisfiability threshold of random formulas (extended abstract)
scientific article; zbMATH DE number 1114008
Bounding the unsatisfiability threshold of random 3-SAT
The unsatisfiability threshold revisited
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT

Cited in

(56)

When does the giant component bring unsatisfiability?
A fast parallel SAT-solver -- efficient workload balancing
Small maximal matchings in random graphs.
On good algorithms for determining unsatisfiability of propositional formulas
On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
Phase transitions in discrete structures
On unique satisfiability and the threshold behavior of randomized reductions
A model of random industrial SAT
Proof of the satisfiability conjecture for large \(k\)
On the satisfiability threshold of formulas with three literals per clause
Super solutions of random \((3 + p)\)-SAT
Maximum independent sets on random regular graphs
Typical case complexity of satisfiability algorithms and the threshold phenomenon
Resolution complexity of random constraint satisfaction problems: Another half of the story
The unsatisfiability threshold revisited
The scaling window of the 2-SAT transition
The unsatisfiability threshold revisited
An improved upper bound on the non-3-colourability threshold
Phase transitions of EXPSPACE-complete problems
The number of satisfying assignments of random regular k-SAT formulas
Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
Selecting Complementary Pairs of Literals
Random instances of problems in NP -- algorithms and statistical physics
Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
scientific article; zbMATH DE number 1114008 (Why is no real title available?)
Approximating the unsatisfiability threshold of random formulas (extended abstract)
The cook-book approach to the differential equation method
Phase transitions of contingent planning problem
Approximating the Satisfiability Threshold for Random k-XOR-formulas
The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
Tail bounds for occupancy and the satisfiability threshold conjecture
scientific article; zbMATH DE number 1445295 (Why is no real title available?)
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
Counting solutions to random CNF formulas
Bounds on the satisfiability threshold for power law distributed random SAT
A new upper bound for random (2 + p)-SAT by flipping two variables
An asymptotic expansion for theq-binomial series using singularity analysis for generating functions
On the solution-space geometry of random constraint satisfaction problems
Satisfiability threshold for power law random 2-SAT in configuration model
Rigorous results for random (2+p)-SAT
Upper bounds on the satisfiability threshold
Satisfiability threshold for random regular \textsc{nae-sat}
One-step replica symmetry breaking of random regular NAE-SAT. II
Searching for (sharp) thresholds in random structures: where are we now?
Faster random k-CNF satisfiability
Counting solutions to random CNF formulas
Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k 3
Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
Sharp phase transitions for the overlap gap property
Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT
Estimating satisfiability
On threshold properties of k-SAT: An additive viewpoint
Regular random \(k\)-SAT: Properties of balanced formulas
The asymptotic k-SAT threshold
On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
Solution clustering in random satisfiability

This page was built for publication: Approximating the unsatisfiability threshold of random formulas

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