[Colloquium] THEORY SEMINAR TODAY: Tom Hayes

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, April 26, 2011
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Tom Hayes

From:		University of New Mexico

Web page:	www.cs.unm.edu/~hayes

Title: 		Faster Liftings for Markov Chains

Abstract:  	A "lifting" of Markov chain is a larger chain obtained by replacing each state of the original chain by a set of states, with transition probabilities defined in such a way that the lifted chain projects down exactly to the original one. It is well known that lifting can potentially speed up the mixing time substantially. Essentially all known examples of efficiently implementable liftings have required a high degree of symmetry in the original chain. Addressing an open question of Chen, Lovasz, and Pak we present the first example of a successful lifting for a complex Markov chain that has been used in sampling algorithms. This chain, firs introduced by Sinclair and Jerrum, samples a leaf uniformly at random in a large tree, given approximate information about the number of leaves in any subtree, and has applications to the theory of approximate counting and to importance sampling in Statistics. Our lifted version of the chain (which, unlike the original one, is non-reversible) gives a significant speedup over the original version whenever the error in the leaf counting estimates is o(1). Our lifting construction, based on flows, is systematic, and we conjecture that it may be applicable to other Markov chains used in sampling algorithms.

Host: 		Laci Babai

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.