[Colloquium] [CS] Colloquia Thomas Hayes/MS Presentation/7/28/03

[Donna Brooms]

This is an announcement of Thomas P. Hayes Master's Presentation.

Date:	Monday, July 28, 2003

Time:	10:00 a.m.

Place:	Ryerson 276

M.S. Candidate:	Thomas P. Hayes

M.S. Paper Title: Faster Convergence for the Glauber Dynamics via 
non-Markovian Couplings and Conditional Independence

Abstract:

The Glauber dynamics is a simple Markov chain widely used in a variety 
of fields for randomly sampling from probability distributions defined 
on large sets of combinatorial strctures.
We analyze the convergence properties of the Glauber dynamics for 
randomly sampling $k$-colorings of a graph on $n$ vertices with maximum 
degree $¥Delta$.
It is not known whether, whenever $k ¥ge ¥Delta + 2$, this chain 
converges to its stationary distribution in polynomial time.
The question is of interest not only for its combinatorial appeal, but 
also because the Glauber dynamics forms the basis for the best known 
randomized approximation algorithm for counting $k$-colorings, a 
¥#P-complete problem.  The question is also of interest in Statistical 
Physics, for its connection to the existence of phase transitions in 
Gibbs distributions.
Prior to our work, the best general results were that the Glauber 
dynamics converges in time $O(n ¥log n)$ for $k > (2 - 10^{-12}) 
¥Delta$, in time $O(n^2 ¥log n)$ for $k > 11/6 ¥Delta$.  Assuming 
$¥Delta = ¥Omega(¥log n)$ and $¥girth = ¥Omega(¥log ¥Delta)$, it was 
recently shown that the Glauber dynamics converges in time $O(n ¥log 
n)$ for $k > ¥alpha^{*}¥Delta$, where $¥alpha^{*} ¥approx 1.498$...
Our main result is that the Glauber dynamics converges in time $O(n 
¥log n)$ for $k > (1 + ¥epsilon) ¥Delta$, assuming $¥Delta = 
¥Omega(¥log n)$ and $¥girth ¥ge 11$.  Our best result under the weaker 
hypotheses that $¥Delta = ¥Omega(1)$ and $¥girth ¥ge 5$ is that the 
convergence time is $O(n ¥log n)$ for $k > ¥beta^{*}¥Delta$, where 
$¥beta^{*} ¥approx 1.763$...
Some of our tools and techniques may be of independent interest. Our 
main result relies on the explicit construction and analysis of a 
non-Markovian coupling; this is the first time a non-Markovian coupling 
has been used to solve an open problem.
Our reductions of the girth requirements rely on a general technique 
for analyzing multilinear functions of conditionally independent random 
variables.
We present a generalization of the Path Coupling Theorem which 
simplifies the construction and analysis of variable-length couplings.

Mr. Hayes' Advisors: Laszlo Babai and Eric Vigoda.

A draft copy of Mr. Hayes' M.S. paper will be available for review in 
Ry 152.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 3498 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20030716/17b8bdc9/attachment.bin