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

DOI10.1145/780542.780577zbMATH Open1192.68333OpenAlexW2010193278MaRDI QIDQ3581271FDOQ3581271

Authors: Yuval Peres, D. 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

Recommendations

• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Bounds on threshold of regular random \(k\)-SAT
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• The satisfiability threshold for non-uniform random 2-SAT
• The asymptotic \(k\)-SAT threshold
• The asymptotic \(k\)-SAT threshold
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• Theory and Applications of Satisfiability Testing
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

Mathematics Subject Classification ID

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

Cited In (39)

• A concentration inequality for the facility location problem
• Maximum independent sets on random regular graphs
• Approximating the unsatisfiability threshold of random formulas (extended abstract)
• A sharp threshold for a random constraint satisfaction problem
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• On smoothed analysis in dense graphs and formulas
• Connectivity and equilibrium in random games
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• A note on random \(k\)-SAT for moderately growing \(k\)
• On threshold properties of \(k\)-SAT: An additive viewpoint
• The power of choice for random satisfiability
• On the lower bounds of random Max 3 and 4-SAT
• Upper bounds on the satisfiability threshold
• Super solutions of random instances of satisfiability
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• A new upper bound for random \((2 + p)\)-SAT by flipping two variables
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Random MAX SAT, random MAX CUT, and their phase transitions
• Theory and Applications of Models of Computation
• A lower bound for the 4-satisfiability threshold
• Theory and Applications of Satisfiability Testing
• Biased random k‐SAT
• Superlogarithmic cliques in dense inhomogeneous random graphs
• Tractability from overparametrization: the example of the negative perceptron
• Lower bounds for random 3-SAT via differential equations
• Proof of the satisfiability conjecture for large \(k\)
• Searching for (sharp) thresholds in random structures: where are we now?
• The pure literal rule threshold and cores in random hypergraphs
• Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
• On the critical exponents of random k‐SAT
• Bounds on threshold of regular random \(k\)-SAT
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
• Counting solutions to random CNF formulas
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT

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

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