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.
Copyright. All Rights Reserved.