  In combinatorial optimization, matroids provide one of the most elegant
structures for algorithm design. This is perhaps best identified by the
Edmonds-Rado theorem relating the success of the simple greedy algorithm to the
anatomy of the optimal basis of a matroid [Edm71; Rad57]. As a response, much
energy has been devoted to understanding a matroid's favorable computational
properties. Yet surprisingly, not much is understood where parallel algorithm
design is concerned. Specifically, while prior work has investigated the task
of finding an arbitrary basis in parallel computing settings [KUW88], the more
complex task of finding the optimal basis remains unexplored. We initiate this
study by reexamining Bor\r{u}vka's minimum weight spanning tree algorithm in
the language of matroid theory, identifying a new characterization of the
optimal basis by way of a matroid's cocircuits as a result. Furthermore, we
then combine such insights with special properties of binary matroids to reduce
optimization in a binary matroid to the simpler task of search for an arbitrary
basis, with only logarithmic asymptotic overhead. Consequentially, we are able
to compose our reduction with a known basis search method of [KUW88] to obtain
a novel algorithm for finding the optimal basis of a binary matroid with only
sublinearly many adaptive rounds of queries to an independence oracle. To the
authors' knowledge, this is the first parallel algorithm for matroid
optimization to outperform the greedy algorithm in terms of adaptive
complexity, for any class of matroid not represented by a graph.
