Seminar Event Detail

Theoretical Computer Science

Date:  Friday, January 15, 2016
Location:  4941 BBB (10:00 AM to 11:00 AM)

Title:  Counting perfect matchings via random matrices

Abstract:   Estimating the number of perfect matchings in a bipartite graph is a well-known computer science problem, and there is a number of algorithms tackling it. Much less is known about estimating this number for a general graphs with an even number of vertices. Essentially, the only known probabilistic estimator for this problem was constructed by Barvinok, who represented the number of perfect matchings via the determinant of a random matrix associated to the graph. Barvinok proved that the multiplicative error of this estimator is at most exponential, and this result cannot be improved for general graphs. We provide conditions on the matrix, under which the Barvinok estimator yields a subexponential error.
Joint work with Alex Samorodnitsky and Ofer Zeitouni.


Speaker:  Mark Rudelson
Institution:  U-M

Event Organizer:      schoeneb


Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact

Back to previous page
Back to UM Math seminars/events page.