[Colloquium] Revised updated: [CS] Colloquia Thomas Hayes/PhD Dissertation/7/28/03
Donna Brooms
donna at cs.uchicago.edu
Wed Jul 16 10:22:17 CDT 2003
This is an announcement of Thomas P. Hayes' Ph.D. Dissertation.
Date: Monday, July 28, 2003
Time: 10:00 a.m.
Place: Ryerson 276
Ph.D. Candidate: Thomas P. Hayes
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.
Advisors: Laszlo Babai and Eric Vigoda.
A draft copy of Mr. Hayes' paper will be available for review in Ry 152.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 3472 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20030716/55ce1eaa/attachment.bin
More information about the Colloquium
mailing list