[Colloquium] FW: Guest Speaker Announcement

[Ponda Barnes]

Reminder!!
 
Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Nayantara Bhatnagar
Speaker home page: http://www-static.cc.gatech.edu/~nand/
 
Date: 5/7/07
Time: 10:00
Location: TTI-C Conference room
 
 
Title: Enhancing the Markov Chain Monte Carlo Method. 
 
Abstract:
The Markov Chain Monte Carlo method is arguably the most powerful
algorithmic tool available for approximate counting problems.  Most known
algorithms for such problems follow the paradigm of defining a 
Markov chain and showing that it mixes rapidly. However, there are natural
counting problems where the obvious Markov chains do not mix rapidly.
Annealing and Simulated Tempering are two heuristic
approaches that can be applied in such situations. Both aim at finding ways
to circumvent bottlenecks that cause Markov chains to mix slowly.  In this
talk, we will explore the power and limitations of
these approaches.
 
We present a simulated annealing based algorithm for the problem of
generating  random binary contingency tables. This problem can be restated
as generating random bipartite graphs with a given degree
sequence.  This is based on joint work with Ivona Bezakova and Eric Vigoda.
On the flip side, we show that in some scenarios, simulated tempering fails
to speed up the mixing of the Markov chain and in fact
no temperature based interpolants for the tempering algorithm can succeed.
This is based on joint work with Dana Randall.
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org
For future TTI-C talks and events, please visit
http://ttic.uchicago.edu/cal/month.php
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070507/8351d541/attachment.html