[Colloquium] Today: Ganapathy/Dissertation Defense/7-21-06

[Margaret Jaffey]

This is a reminder about Murali's defense today.


Department of Computer Science/The University of Chicago

				*** Dissertation Defense ***


Candidate:  Murali Krishnan Ganapathy

Date:  Friday, July 21, 2006

Time and Location:  12.30 p.m. in Ryerson 255

Title:  Robust Mixing

Abstract:
How many times should a card shuffler shuffle to get the cards shuffled?
Convergence rate questions like these are central to the theory of  
finite
Markov Chains and arise in diverse fields including Physics, Computer
Science as well as Biology. This thesis introduces two new approaches
to estimating mixing times: robust mixing time of a Markov Chain and
Markovian product of Markov Chains.

The "robust mixing time" of a Markov Chain is the notion of mixing time
which results when the steps of the Markov Chain are interleaved with
that of an oblivious adversary under reasonable assumptions on the
intervening steps. We develop the basic theory of robust mixing and
use it to give a simpler proof of the limitations of reversible  
liftings of a
Markov Chain due to Chen, Lovasz and Pak (1999). We also use this
framework to improve the mixing time estimate of the cyclic-to-random
transposition process (a non-Markovian process) given by Mossel,
Peres and Sinclair (2004).

The "Markovian product" of Markov Chains is like the direct product,
except for a controlling Markov Chain which helps decide which component
should be updated. Direct products as well as wreath products of Markov
Chains are special cases. We show how a coupon collector type of  
analysis
can be used to estimate the mixing times of these product chains under
various distance measures. Using this, we derive L^2-mixing time
estimates of a Cayley walk on Complete Monomial Groups, which are
only a factor 2 worse than those obtained by Schoolfield (2002) using
representation theory. Together with robust mixing time estimates, we
also estimate mixing times of Markov Chains which arise in the context
of Sandpile groups.

In the case of Lamp Lighter Chains, we are lead to estimating moment
generating functions of occupancy measures of a Markov Chain.
We sharpen a previous estimate, due to Peres and Revelle (2004), of how
long it takes to visit all the states of a Markov Chain, and answer some
questions raised by them.

Candidate's Advisor: Prof. Laszlo Babai

A draft copy of Mr. Ganapathy's dissertation is available  in Ry 161A.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060721/53641523/attachment.htm