Breaking the n‾√ Barrier: New Parallel Algorithms for Finding a Matroid Basis

Over 40 years ago, Karp, Upfal, and Wigderson posed a central open question in parallel computation: how many adaptive rounds are needed to find a basis of a matroid using only independence queries? Their pioneering work gave an upper bound of O(n‾√) rounds and a lower bound of roughly Ω(n1/3) rounds---bounds that have stood unchanged ever since.

In this talk, I will present recent progress on this classic problem. We give a new parallel algorithm that, with high probability, finds a matroid basis in O(n3/7) rounds, breaking the long-standing O(n‾√) barrier. For the important special case of partition matroids, we obtain an optimal O(n1/3)

-round algorithm, settling their complexity. Our approach introduces a new matroid decomposition technique which may be of independent interest, and also yields faster parallel algorithms for the classic matroid intersection problem, among others.

Based on joint work with Sanjeev Khanna and Junkai Song (Penn).