BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/114
DTSTAMP:20230914T125911Z
SUMMARY:Approximate Counting\, Uniform Generation and Rapidly Mixing Markov
  Chains
DESCRIPTION:Speaker: Girish Varma\nSchool of Technology and Computer Scienc
 e\nTata Institute of Fundamental Research\nHomi Bhabha Road\n\nAbstract: \
 nMost 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 unifo
 rm generation could be NP-Hard even if decision or search could be done ef
 ficiently. M. Jerrum and A. Sinclair used the Markov chain Monte Carlo met
 hod to approximately count the number of perfect matchings of a dense bipa
 rtite graph. They reduced approximate counting to almost uniform generatio
 n of perfect matchings. Almost uniform generation was done by starting wit
 h an arbitrary solution\, and repeatedly making random modifications to it
 . This process was modeled as a Markov chain\, with a stationary distribut
 ion 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 defi
 ning canonical paths between every pair of states in the chain.\n
URL:https://www.tcs.tifr.res.in/web/events/114
DTSTART;VALUE=DATE:20100906
LOCATION:AG-69
END:VEVENT
END:VCALENDAR