  We provide an algorithm which, with high probability, maintains a
$(1-\epsilon)$-approximate maximum flow on an undirected graph undergoing
$m$-edge additions in amortized $m^{o(1)} \epsilon^{-3}$ time per update. To
obtain this result, we provide a more general algorithm that solves what we
call the incremental, thresholded $p$-norm flow problem that asks to determine
the first edge-insertion in an undirected graph that causes the minimum
$\ell_p$-norm flow to decrease below a given threshold in value. Since we solve
this thresholded problem, our data structure succeeds against an adaptive
adversary that can only see the data structure's output. Furthermore, since our
algorithm holds for $p = 2$, we obtain improved algorithms for dynamically
maintaining the effective resistance between a pair of vertices in an
undirected graph undergoing edge insertions.
  Our algorithm builds upon previous dynamic algorithms for approximately
solving the minimum-ratio cycle problem that underlie previous advances on the
maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22]
as well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC
'23]. Instead of using interior point methods, which were a key component of
these recent advances, our algorithm uses an optimization method based on
$\ell_p$-norm iterative refinement and the multiplicative weight update method.
This ensures a monotonicity property in the minimum-ratio cycle subproblems
that allows us to apply known data structures and bypass issues arising from
adaptive queries.
