Algorithms and Complexity Seminar
Thursday, February 23, 2006, 4-5:15pm in 32-G575.
Randomized Algebraic Algorithms for Matroid and Matching Problems
Nick Harvey (MIT)
The task of finding a maximum matching in a graph is one of the
classical problems in the theory of algorithms, inspiring the
definition of the class P. Till recently, the fastest algorithm for
this task took O(n^2.5) steps in an n vertex (dense) graph. But an
exciting development due to Mucha and Sankoswki (FOCS '04) dropped the
running time to O(n^w) where w < 2.38 is the exponent of matrix
multiplication, with a randomized algorithm. However, their result was
quite complicated, relying on certain structural decompositions of
graphs and complicated data structures to maintain certain properties
dynamically.
In this talk, I will present two new results: The first is a simple
randomized algorithm achieving the same result, allowing for a
self-contained presentation of this result. The second is an extension
of this algorithm to the task of matroid intersection (for linear
matroids over any field).
Host: Madhu Sudan