'Counting Matchings with Markov Chain Monte Carlo' -
Perfect matchings pair each vertex in a graph with exactly one adjacent vertex. The algorithmic problem of counting all perfect matchings in a bipartite graph is famously intractable---it is the prototypical #P-complete problem. Nevertheless, a randomized algorithm due to Jerrum, Sinclair, and Vigoda can efficiently approximately count the number of perfect matchings in a bipartite graph, via a classic application of the Markov Chain Monte Carlo (MCMC) technique. We will take a brief tour through matching theory, computational complexity, and MCMC for sampling and counting combinatorial structures, before describing progress on the problem of approximately counting perfect matchings in general (non-bipartite) graphs.
Thursday, November 7, 2019 at 4:40pm to 5:30pm
Eliot Hall, 314
3203 Southeast Woodstock Boulevard, Portland, Oregon 97202-8199
Reed Community Members
If you are a member of the Reed community, you MUST LOG IN to see events that are open ONLY to the Reed community. Log in with your Reed ID (your Kerberos account information). If you don’t remember your account username or password, go to reed.edu/cis/help/kerberos.html.Log in with Reed ID