  In this paper, we study the tradeoff between the approximation guarantee and
adaptivity for the problem of maximizing a monotone submodular function subject
to a cardinality constraint. The adaptivity of an algorithm is the number of
sequential rounds of queries it makes to the evaluation oracle of the function,
where in every round the algorithm is allowed to make polynomially-many
parallel queries. Adaptivity is an important consideration in settings where
the objective function is estimated using samples and in applications where
adaptivity is the main running time bottleneck. Previous algorithms achieving a
nearly-optimal $1 - 1/e - \epsilon$ approximation require $\Omega(n)$ rounds of
adaptivity. In this work, we give the first algorithm that achieves a $1 - 1/e
- \epsilon$ approximation using $O(\ln{n} / \epsilon^2)$ rounds of adaptivity.
The number of function evaluations and additional running time of the algorithm
are $O(n \mathrm{poly}(\log{n}, 1/\epsilon))$.
