2026-09-08T02:22:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26513 2026-09-05T19:46:11Z ddc:004 open_access

An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases Khanna, Sanjeev Putterman, Aaron Song, Junkai parallel algorithms matroids We study the parallel (adaptive) complexity of the classic problem of finding a basis in an n-element matroid, given access via an 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(√n) adaptive rounds suffice for any matroid, and that Ω̃(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 Õ(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 Õ(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. Specifically, our framework introduces three new ideas: 1) A new subset-based decomposition that provides precise guarantees on how random circuits intersect groups of elements, yet remains computable in few adaptive rounds. 2) A new method for identifying and removing redundant elements in bulk, based on short circuit witnesses that certify redundancy across large portions of the matroid. 3) An adaptive early-stopping strategy that uses the evolving structure of the matroid to decide when to contract or delete, preventing wasted rounds. Each of these contributions, in isolation, already yields meaningful improvements over the round complexity achieved in KPS; their combination enables our main result of Õ(n^{3/7}) rounds. As further consequences, incorporating our improved basis-finding algorithm into known reductions yields an Õ(n^{17/21})-round parallel algorithm for matroid intersection, as well as an Õ(n^{3/7})-round parallel algorithm for approximate monotone submodular maximization under a matroid constraint. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sanjeev Khanna and Aaron Putterman and Junkai Song 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.124 urn:nbn:de:0030-drops-265130 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.124 eng https://creativecommons.org/licenses/by/4.0/legalcode