Tata Institute of Fundamental Research

How Hard is it to Marry at Random?

Student Seminar
Speaker: Girish Varma School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Date: Friday, 23 Oct 2009 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods), are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample from the desired distribution. The quality of the sample improves as a function of the number of steps. We will use such a thing for generating a random perfect matching.

Reference :

Approximating the permanent M Jerrum, A Sinclair - SIAM journal on computing, 1989 - link.aip.org

How hard is it to marry at random? AZ Broder - Proceedings of the eighteenth annual ACM symposium …, 1986 - portal.acm.org