Tata Institute of Fundamental Research
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains
Project Seminar
Speaker:
Girish Varma
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Monday, 6 Sep 2010 (all day)
Venue:
AG-69
(Scan to add to calendar)
Abstract:
Most algorithmic problems could be viewed as questions being asked about a natural binary relation and we can classify them into decision, search, uniform generation and counting. For some relations, counting and uniform generation could be NP-Hard even if decision or search could be done efficiently. M. Jerrum and A. Sinclair used the Markov chain Monte Carlo method to approximately count the number of perfect matchings of a dense bipartite graph. They reduced approximate counting to almost uniform generation of perfect matchings. Almost uniform generation was done by starting with an arbitrary solution, and repeatedly making random modifications to it. This process was modeled as a Markov chain, with a stationary distribution that is uniform on the set of perfect matchings. The rapid convergence of the chain towards its stationary distribution, was proved by bounding a quantity called conductance. This was done using a novel method of defining canonical paths between every pair of states in the chain.
| Speaker: | Girish Varma School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Monday, 6 Sep 2010 (all day) |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
Most algorithmic problems could be viewed as questions being asked about a natural binary relation and we can classify them into decision, search, uniform generation and counting. For some relations, counting and uniform generation could be NP-Hard even if decision or search could be done efficiently. M. Jerrum and A. Sinclair used the Markov chain Monte Carlo method to approximately count the number of perfect matchings of a dense bipartite graph. They reduced approximate counting to almost uniform generation of perfect matchings. Almost uniform generation was done by starting with an arbitrary solution, and repeatedly making random modifications to it. This process was modeled as a Markov chain, with a stationary distribution that is uniform on the set of perfect matchings. The rapid convergence of the chain towards its stationary distribution, was proved by bounding a quantity called conductance. This was done using a novel method of defining canonical paths between every pair of states in the chain.