Satisfiability thresholds for random models of constraint satisfaction problems

Michael Molloy
University of Toronto
Computer Science

A few years ago, the speaker introduced a family of models for random constraint satisfaction problems,
and characterized which of these models exhibit (possibly non-sharp) satisfiability thresholds.
In this talk, we discuss more recent work in which we provide more information
about the location of these thresholds. In particular, we characterize which models
a.s. remain satisfiable for theta(n) steps beyond the appearance of a giant component
in the underlying constraint hypergraph.

This is a collaboration with Dimitris Achlioptas and Jeong Han Kim.

Presentation (PDF File)

Back to Phase Transitions And Algorithmic Complexity