<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: Tuesday, April 8, 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">Markov Chain Monte Carlo Algorithms</font><span style="color: black; "><span><font class="Apple-style-span" face="Helvetica" size="3"> </font> </span></span></span></div><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"><o:p></o:p></p><span>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><p class="MsoNormal">---------------------------------------------------------</p><p class="MsoNormal">Host:<span class="Apple-tab-span" style="white-space: pre; "> </span>Stuart Kurtz</p></body></html>