7/19/2004 Sharp thresholds for random constraint satisfaction problems; Michael Molloy - University of Toronto at Scarborough

From: Monika Roberts (monikar@microsoft.com)
Date: Fri Jul 16 2004 - 23:21:50 PDT

  • Next message: Kelli McGee \(Kelly Services Inc\): "7/21/2004 Online Auctions, Strategyproofness and Random Valuations; Mohammad Taghi Hajiaghayi, MIT and Microsoft Research"

    Apologies for the short notice. Please let me know if you would like to
    attend, so I may notify the building 113 receptionist. Thank you, Monika

    You are invited to attend...
    ************************************************************************
    *****************************
    WHO: Michael Molloy
    AFFILIATION: University of Toronto, Department of Computer Science
    TITLE: Sharp thresholds for random constraint
    satisfaction problems
    WHEN: Mon 7/19/2004
    WHERE: 113/1021 Research Lecture Room
    TIME: 3:30PM-5:00PM
    HOST: Jeong Han Kim
    MSRNS: For Live/On Demand viewing availability check
    http://resnet/msrn
    ************************************************************************
    ******************************
    ABSTRACT:

    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.

    BIO:
    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.

  • Next message: Kelli McGee \(Kelly Services Inc\): "7/21/2004 Online Auctions, Strategyproofness and Random Valuations; Mohammad Taghi Hajiaghayi, MIT and Microsoft Research"

    This archive was generated by hypermail 2.1.6 : Fri Jul 16 2004 - 23:22:23 PDT