  In this paper we study submodular maximization under a matroid constraint in
the adaptive complexity model. This model was recently introduced in the
context of submodular optimization in [BS18a] to quantify the information
theoretic complexity of black-box optimization in a parallel computation model.
Informally, the adaptivity of an algorithm is the number of sequential rounds
it makes when each round can execute polynomially-many function evaluations in
parallel. Since submodular optimization is regularly applied on large datasets
we seek algorithms with low adaptivity to enable speedups via parallelization.
Consequently, a recent line of work has been devoted to designing constant
factor approximation algorithms for maximizing submodular functions under
various constraints in the adaptive complexity model [BS18a, BS18b, BBS18,
BRS19, EN19, FMZ19, CQ19, ENV18, FMZ18].
  Despite the burst in work on submodular maximization in the adaptive
complexity model the fundamental problem of maximizing a monotone submodular
function under a matroid constraint has remained elusive. In particular, all
known techniques fail for this problem and there are no known constant factor
approximation algorithms whose adaptivity is sublinear in the rank of the
matroid $k$ or in the worst case sublinear in the size of the ground set $n$.
  In this paper we present an approximation algorithm for the problem of
maximizing a monotone submodular function under a matroid constraint in the
adaptive complexity model. The approximation guarantee of the algorithm is
arbitrarily close to the optimal $1-1/e$ and it has near optimal adaptivity of
$O(\log(n)\log(k))$. This result is obtained using a novel technique of
adaptive sequencing which departs from previous techniques for submodular
maximization in the adaptive complexity model.
