On the Parallel Complexity of Finding a Matroid Basis

A fundamental question in parallel computation, posed by Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988), asks: given only independence-oracle access to a matroid on n elements, how many rounds are required to find a basis using only polynomially many queries? This question generalizes, among others, the complexity of finding bases of linear spaces, partition matroids, and spanning forests in graphs. In their work, they established an upper bound of O(√n) rounds and a lower bound of widetildeOmega(n1/3) rounds for this problem, and these bounds have remained unimproved since then. In this work, we make the first progress in narrowing this gap by designing a parallel algorithm that finds a basis of an arbitrary matroid in tildeO(n7/15) rounds (using polynomially many independence queries per round) with high probability, surpassing the long-standing O(√n) barrier. Our approach introduces a novel matroid decomposition technique and other structural insights that not only yield this general result but also lead to a much improved new algorithm for the class of partition matroids (which underlies the widetildeOmega(n1/3) lower bound of Karp, Upfal, and Wigderson). Specifically, we develop an tildeO(n1/3)-round algorithm, thereby settling the round complexity of finding a basis in partition matroids.