Candidate Talk: Query Lower Bounds for Matroids via Group Representations

Finding an common independent set in two matroids is one of
the classical problems of combinatorial optimization, including
the well-known bipartite matching problem as a special case.
In the early 1970s, algorithms for this problem were discovered
that use O(n3) queries for matroids on n elements. In Welsh’s
1976 text on matroid theory, he asked the question of whether
these algorithms are optimal. In the following thirty years,
no non-trivial lower bounds were found.

In this talk, I will present the first lower bound for this problem.
We show that (log2 3)*n queries are necessary for certain matroids.
The arguments are based on communication complexity and representation
theory of the symmetric group.

Speaker Details

Nicholas Harvey is a doctoral student in theoretical computer science at MIT, working with Prof. David Karger. His research interests are in combinatorial algorithms and distributed systems. He has a BMath in Computer Science and Combinatorial Optimization from the University of Waterloo. He has also worked at Microsoft as a developer in the Active Directory group and on the Herald project in the Systems & Networking group at Microsoft Research.

Date:
Speakers:
Nick Harvey
Affiliation:
MIT