
Breaking the √n Barrier: New Parallel Algorithms for Finding a Matroid Basis
Aaron (Louie) Putterman of Harvard University presents new results on a parallel computation problem open since Karp, Upfal, and Wigderson's work over 40 years ago: how many adaptive rounds of independence queries are needed to find a basis of a matroid. He introduces an algorithm that finds a basis in O(n^3/7) rounds with high probability, improving on the long-standing O(sqrt n) bound, and shows that for partition matroids the optimal round complexity is O(n^1/3), settling that special case. The talk explains the new matroid decomposition technique behind these results and its further applications to parallel algorithms for matroid intersection. Delivered as an Institute for Advanced Study Computer Science/Discrete Mathematics Seminar, the talk presents joint work with Sanjeev Khanna and Junkai Song of the University of Pennsylvania, aimed at an audience already familiar with matroid theory and parallel complexity.