CS 298-2
Theory Seminar
Tom Hayes
Toyota Technological Institute at Chicago
Consider the problem of generating a proper k-coloring of a given
graph G, uniformly at random from all such colorings (adjacent vertices must
receive different colors). When k is larger than the maximum degree of G, it
is trivial to construct such a coloring via a greedy algorithm. In sharp
contrast, the problem of sampling such a coloring uniformly at random
remains unsolved.
Following the Markov Chain Monte Carlo approach, we study a very simple Markov chain on proper graph colorings, whose distribution tends asymptotically towards uniform. The chain is said to be``rapidly mixing'' when the convergence time depends polynomially on the size of the graph. It is widely conjectured that our simple chain is rapidly mixing whenever the number of colors exceeds the maximum degree.
I will discuss partial results in this direction, especially those
in my papers from STOC and FOCS 2003 (links below).
The focus will be on recent advances in the coupling method,
a general technique for proving rapid mixing.
Links to papers:
http://www.cs.uchicago.edu/~hayest/papers/GirthFive
http://www.cs.uchicago.edu/~hayest/papers/NonMarkovianColorings
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 algorithms.