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.