  In large-data applications, it is desirable to design algorithms with a high
degree of parallelization. In the context of submodular optimization, adaptive
complexity has become a widely-used measure of an algorithm's "sequentiality".
Algorithms in the adaptive model proceed in rounds, and can issue polynomially
many queries to a function $f$ in each round. The queries in each round must be
independent, produced by a computation that depends only on query results
obtained in previous rounds.
  In this work, we examine two fundamental variants of submodular maximization
in the adaptive complexity model: cardinality-constrained monotone
maximization, and unconstrained non-mono-tone maximization. Our main result is
that an $r$-round algorithm for cardinality-constrained monotone maximization
cannot achieve an approximation factor better than $1 - 1/e - \Omega(\min \{
\frac{1}{r}, \frac{\log^2 n}{r^3} \})$, for any $r < n^c$ (where $c>0$ is some
constant). This is the first result showing that the number of rounds must blow
up polynomially large as we approach the optimal factor of $1-1/e$.
  For the unconstrained non-monotone maximization problem, we show a positive
result: For every instance, and every $\delta>0$, either we obtain a
$(1/2-\delta)$-approximation in $1$ round, or a
$(1/2+\Omega(\delta^2))$-approximation in $O(1/\delta^2)$ rounds. In particular
(and in contrast to the cardinality-constrained case), there cannot be an
instance where (i) it is impossible to achieve an approximation factor better
than $1/2$ regardless of the number of rounds, and (ii) it takes $r$ rounds to
achieve a factor of $1/2-O(1/r)$.
