How Hard is it to Marry at Random?

Girish Varma School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Friday, 23 Oct 2009 (all day)
A-212 (STCS Seminar Room)
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 -

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