DEPARTMENT OF COMPUTER SCIENCE COLLOQUIUM SERIES

SPEAKER
---------
Dr. Daniel Stefankovic
Department of Computer Science
University of Rochester


TIME AND LOCATION
------------------
Tuesday, October 20, 2009, 1pm
70-1435


TALK TITLE
-------------
Counting and sampling using Markov chains


ABSTRACT
---------
Markov chains are a popular tool for sampling from complex 
distributions, for example, combinatorial configurations, statistical 
physics models, posterior distributions in Bayesian inference, etc. This 
talk will give an overview of theoretical foundations of this area, 
focusing on two issues:
    1. notions of "mixing time", that is, how many steps of a Markov 
chain are needed to achieve various goals?
    2. connection between counting and sampling--a sophisticated 
extension of Monte Carlo techniques that allows approximate computation 
of useful quantities, for example, values of the partition function in 
statistical physics models.


BIOGRAPHY
----------
Daniel Stefankovic received his Ph.D. in computer science from the 
University of Chicago in 2005. In the same year he joined the Computer 
Science department at the University of Rochester. His research area is 
the theory of computing; it includes computational topology (classical 
algorithmic problems on simple curves on surfaces, graph drawing); 
Markov chain Monte Carlo sampling; extremal combinatorics; algorithmic 
game theory; algorithmic coding theory; computational learning; and 
applications of discrete and continuous Fourier transforms.