research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleThe Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements
Bibtex cite IDRACTI-RU1-2006-23
Journal Oxford University
Year published 2006
Pages 159-178
Note Computational Complexity and Statistical Physics
One of the most challenging problems in probability and complexity theory is to establish and determine the satisfiability threshold, or phase transition, for random k-SAT instances: Boolean formulas consisting of clauses with exactly k literals. As the previous part of the volume has explored, empirical observations suggest that there exists a critical ratio of the number of clauses to the number of variables, such that almost all randomly generated formulas with a higher ratio are unsatisfiable while almost all randomly generated formulas with a lower ratio are satisfiable. The statement that such a crossover point really exists is called the satisfiability threshold conjecture. Experiments hint at such a direction, but as far as theoretical work is concerned, progress has been difficult. In an important advance, Friedgut [23] showed that the phase transition is a sharp one, though without proving that it takes place at a “fixed” ratio for large formulas. Otherwise, rigorous proofs have focused on providing successively better upper and lower bounds for the value of the (conjectured) threshold. In this chapter, our
Kirousis, Lefteris
Stamatiou, Yannis
Zito, Michele
j4.pdf (main file)
Publication ID73