Abstract
Satisfiability thresholds for random models of constraint satisfaction problems
Michael Molloy
University of Toronto
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.
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.
No video available