1/14/2004 Variable-length Path Coupling; Tom Hayes - Toyota Institute      

From: Rosa Teorell (rosat@microsoft.com)
Date: Tue Jan 13 2004 - 13:22:18 PST

  • Next message: Paul Beame: "Theorist's Toolkit heads up"

    You are invited to attend...

    *****************************************************************************************************

    WHO: Tom Hayes

    AFFILIATION: Toyota Institute

    TITLE: Variable-length Path Coupling

    WHEN: Wed 1/14/2004

    WHERE: 113/1021 Research Lecture Room, Microsoft Research

    TIME: 10:30AM-12:00PM

    HOST: Jennifer Chayes

    ******************************************************************************************************

    ABSTRACT:

    The Coupling Method is a powerful and classical technique for proving rapid convergence of Markov chains. In the analysis of couplings, one typically chooses a suitable metric on the state space, and attempts to show that after one step of the chain, the expected distance between the coupled chains decreases.

     

    I will discuss a new technique for proving rapid mixing by analyzing the expected distance after a variable number of steps (the number of steps must be a stopping time with respect to the chains). Our main result is a generalization of the so-called Path Coupling Theorem of Bubley and Dyer to this new setting. As an application, I will present a new upper bound for randomly sampling graph colorings

     

    BIO:

    Tom Hayes is currently a Visiting Assistant Professor at the Toyota Technological Institute at Chicago. He received his B.A. from Michigan State University in 1993, and his M.S. in Mathematics and Ph.D. in Computer Science from the University of Chicago in 1994 and 2003, respectively. One of his papers, titled "Randomly Coloring Graphs of Girth at Least Five" won the 2003 Danny Lewin Best Student Paper Award at the IEEE Symposium on Theory of Computing (STOC). Tom's research interests include rapidly mixing Markov chains, randomized algorithms, concentration inequalities for random processes, communication complexity, quantum computing and graph theory.


    _______________________________________________
    Theory-group mailing list
    Theory-group@cs.washington.edu
    http://mailman.cs.washington.edu/mailman/listinfo/theory-group

  • Next message: Paul Beame: "Theorist's Toolkit heads up"

    This archive was generated by hypermail 2.1.6 : Tue Jan 13 2004 - 13:22:57 PST