Sharp thresholds for random constraint satisfaction problems

We consider a wide family of models for random constraint satisfaction problems. This family includes random k-SAT, random k-colourability and many other well-studied generalizations. Our goal is to determine precisely which members of this family have sharp thresholds of satisfiability, in the sense (formalized by Friedgut) that the probability of satisfiability drops suddenly from 1-o(1) to o(1) as the number of constraints increases. In doing so, we want to understand what sorts of features can cause models to have coarse thresholds rather than sharp ones.

In this talk, I’ll report some early progress towards this goal. This includes: (1) a proof that, for any simple connected graph H (on at least 2 vertices), the property “is homomorphic to H” has a sharp threshold iff H has a triangle; (2) a characterization of which models from a natural subfamily (the so-called (d,k,t)-models) have sharp thresholds.

This is joint work with Hamed Hatami.

Speaker Details

Michael Molloy is a Full Professor in the Department of Computer Science at the University of Toronto. He received his PhD (algorithms, combinatorics and optimization) from the Department of Mathematics at Carnegie Mellon University in 1994.Michael Molloy’s research centers on combinatorics and theoretical computer science, focusing most often on probabilistic aspects of these fields.

Date:
Speakers:
Michael Molloy
Affiliation:
University of Toronto
    • Portrait of Jeff Running

      Jeff Running