An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910192297312256 |
|---|---|
| author | Khanna, Sanjeev Putterman, Aaron Song, Junkai |
| author_facet | Khanna, Sanjeev Putterman, Aaron Song, Junkai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03979 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases Khanna, Sanjeev Putterman, Aaron Song, Junkai Data Structures and Algorithms Computational Complexity 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. |
| title | An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2605.03979 |