On the Complexity of Dynamic Submodular Maximization
  We study dynamic algorithms for the problem of maximizing a monotone
submodular function over a stream of $n$ insertions and deletions. We show that
any algorithm that maintains a $(0.5+\epsilon)$-approximate solution under a
cardinality constraint, for any constant $\epsilon>0$, must have an amortized
query complexity that is $\mathit{polynomial}$ in $n$. Moreover, a linear
amortized query complexity is needed in order to maintain a $0.584$-approximate
solution. This is in sharp contrast with recent dynamic algorithms of [LMNF+20,
Mon20] that achieve $(0.5-\epsilon)$-approximation with a
$\mathsf{poly}\log(n)$ amortized query complexity.
  On the positive side, when the stream is insertion-only, we present efficient
algorithms for the problem under a cardinality constraint and under a matroid
constraint with approximation guarantee $1-1/e-\epsilon$ and amortized query
complexities $\smash{O(\log (k/\epsilon)/\epsilon^2)}$ and
$\smash{k^{\tilde{O}(1/\epsilon^2)}\log n}$, respectively, where $k$ denotes
the cardinality parameter or the rank of the matroid.
