<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">DEPARTMENT OF COMPUTER SCIENCE<div><br class="webkit-block-placeholder"></div><div>UNIVERSITY OF CHICAGO</div><div><br class="webkit-block-placeholder"></div><div>Date: Wednesday, April 16, 2008</div><div>Time: 12:00 p.m.</div><div>Place: Kent 120, 1020 E. 58th Street</div><div><br class="webkit-block-placeholder"></div><div>----------------------------------------------------------</div><div><br class="webkit-block-placeholder"></div><div>Speaker:<span class="Apple-tab-span" style="white-space: pre; "> </span>Eric Vigoda</div><div><br class="webkit-block-placeholder"></div><div>From:<span class="Apple-tab-span" style="white-space: pre; "> </span>Georgia Institute of Technology</div><div><br class="webkit-block-placeholder"></div><div>Web page:<span class="Apple-tab-span" style="white-space: pre; "> </span><a href="http://www.cc.gatech.edu/~vigoda/">http://www.cc.gatech.edu/~vigoda/</a></div><div><br class="webkit-block-placeholder"></div><div>Title: <span class="Apple-style-span" style="font-family: 'Times New Roman'; font-size: 16px; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">Markov Chain Monte Carlo
Algorithms</span></font><span style="color:black"><span style="mso-tab-count:1"><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"> </span></font> </span></span></span></div><!--StartFragment--><div><br class="webkit-block-placeholder"></div><div>Abstract: In this talk, I'll look at the design and analysis of
Markov Chain Monte Carlo (MCMC) algorithms. In the first part of the talk
I will present MCMC algorithms which yielded the first polynomial-time
algorithms for important combinatorial problems. In particular, I'll present
MCMC algorithms for sampling/counting 0-1 contingency tables with arbitrary
row/column sums, and estimating the permanent of a non-negative matrix. These algorithms
require a sophisticated simulated annealing type approach, with a sequence of
problem instances starting from a trivial instance (infinite temperature) and slowly moving to the instance of interest (zero
temperature). </div><p class="MsoNormal" style="mso-pagination:none;mso-layout-grid-align:none;
text-autospace:none"><o:p></o:p></p>
<span style="">In the second part of the talk I will discuss
the use of MCMC algorithms in evolutionary biology for phylogenetic reconstruction.
I'll present some recent work in that setting where heterogeneous data
causes the MCMC algorithms to be slow to converge to the desired posterior
distribution.</span><!--EndFragment-->
<p class="MsoNormal">---------------------------------------------------------</p><p class="MsoNormal">Host:<span class="Apple-tab-span" style="white-space: pre; "> </span>Stuart Kurtz</p></body></html>