A fundamental question in parallel computation, posed by Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988), asks: \emph{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(\sqrt{n})$ rounds and a lower bound of $\widetildeΩ(n^{1/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 $\tilde{O}(n^{7/15})$ rounds (using polynomially many independence queries per round) with high probability, surpassing the long-standing $O(\sqrt{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 \emph{partition matroids} (which underlies the $\widetildeΩ(n^{1/3})$ lower bound of Karp, Upfal, and Wigderson). Specifically, we develop an $\tilde{O}(n^{1/3})$-round algorithm, thereby settling the round complexity of finding a basis in partition matroids.

翻译：Karp、Upfal和Wigderson（FOCS 1985，JCSS 1988）提出的并行计算中的一个基本问题是：\emph{给定对n个元素上拟阵的独立性预言机访问，在每轮仅使用多项式次查询的情况下，需要多少轮才能找到一个基？}该问题推广了线性空间基、划分拟阵基以及图中生成森林的寻找复杂度等。在他们的工作中，他们为该问题建立了O(√n)轮的上界和Ω̃(n^{1/3})轮的下界，且这些界自提出以来一直未被改进。在本工作中，我们首次通过设计一种并行算法来缩小这一差距，该算法以高概率在Õ(n^{7/15})轮内（每轮使用多项式次独立性查询）找到任意拟阵的一个基，突破了长期存在的O(√n)障碍。我们的方法引入了一种新颖的拟阵分解技术和其他结构洞见，不仅得到了这一普遍结果，还为\emph{划分拟阵}类（Karp、Upfal和Wigderson的Ω̃(n^{1/3})下界的基础）带来了显著改进的新算法。具体而言，我们开发了一种Õ(n^{1/3})轮算法，从而确定了划分拟阵中寻找基的轮复杂度。