AI summaryⓘ
The authors solved a long-standing question about how quickly a computer can find a basis of a matroid using many processors at once. They created an algorithm that works in about n^(1/3) steps times a small logarithmic factor, which is almost as fast as the known theoretical minimum. This matches earlier lower bounds from Karp, Upfal, and Wigderson up to a small difference. Their work clarifies the limits of parallel computation for this problem.
matroid basisparallel complexityalgorithmround complexityKarp-Upfal-WigdersonFOCSJCSSlower boundparallel computinglogarithmic factors
Authors
Sanjeev Khanna, Aaron Putterman, Junkai Song
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.