Seminar Details

Over 40 years ago, Karp, Upfal, and Wigderson initiated the study of a fundamental question in parallel computation: how many adaptive rounds are required to find a basis of a matroid using only polynomially many independence queries (that is, queries that test whether a set is independent)? Their pioneering work established an upper bound of O(\sqrt{n}) rounds and a lower bound of roughly n^{1/3} rounds; these bounds have remained unchanged since.

In this talk, I will present recent progress on this question. We give a near-optimal algorithm that runs in O(n^{1/3} log^{1/3} n) rounds. This essentially resolves the long-standing question of the adaptive round complexity of matroid basis finding and also leads to faster parallel algorithms for the matroid intersection problem.

This is joint work with Sanjeev Khanna (NYU) and Aaron (Louie) Putterman (Harvard).