The threshold for random k-SAT is 2 k (ln 2 - O(k))

DOI10.1145/780542.780577zbMath1192.68333OpenAlexW2010193278MaRDI QIDQ3581271

Yuval Peres, Demetrios Achlioptas

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780577

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05)

Related Items (17)

A sharp threshold for a random constraint satisfaction problem ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Super Solutions of Random Instances of Satisfiability ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Maximum independent sets on random regular graphs ⋮ A concentration inequality for the facility location problem ⋮ Counting Solutions to Random CNF Formulas ⋮ Tractability from overparametrization: the example of the negative perceptron ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ Connectivity and equilibrium in random games ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs ⋮ Random MAX SAT, random MAX CUT, and their phase transitions ⋮ On smoothed analysis in dense graphs and formulas ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon

This page was built for publication: The threshold for random k-SAT is 2 ^k (ln 2 - O(k))