A Near-Optimal Parallel Algorithm for Finding Matroid Bases

Abstract

We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our algorithm runs in $O(n^{1/3}{\log }^{1/3}n)$ rounds, matching the lower bound of KUW up to a ${\log }^{2/3}(n)$ factor.