An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
2026-05-05 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Complexity
AI summaryⓘ
The authors study how quickly one can find a basis in a matroid by asking questions about which sets of elements are independent, using multiple queries in parallel rounds. Earlier research showed that it takes about the square root of the number of elements rounds to find a basis and that at least the cube root of that number is needed for some cases. A recent improvement reduced this to around n to the 7/15 power rounds. The authors improve this further to about n to the 3/7 power rounds by developing a new way to analyze how dependencies between elements work together, rather than looking at them individually.
matroidbasisindependence oracleadaptive complexityparallel queriesrandom circuitspartition matroidalgorithm analysisquery complexity
Authors
Sanjeev Khanna, Aaron Putterman, Junkai Song
Abstract
We study the parallel (adaptive) complexity of the classic problem of finding a basis in an $n$-element matroid, given access via an \emph{independence oracle}. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS~1985, JCSS~1988; hereafter KUW) initiated this study, showing that $O(\sqrt{n})$ adaptive rounds suffice for any matroid, and that $\widetildeΩ(n^{1/3})$ rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS~2025; hereafter KPS) achieved $\widetilde O(n^{7/15})$ rounds, the first improvement since~KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in $\widetilde O(n^{3/7})$ rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously.