  In 2015, it was shown that reachability for arbitrary directed graphs can be
updated by first-order formulas after inserting or deleting single edges.
Later, in 2018, this was extended for changes of size $\frac{\log n}{\log \log
n}$, where $n$ is the size of the graph. Changes of polylogarithmic size can be
handled when also majority quantifiers may be used.
  In this paper we extend these results by showing that, for changes of
polylogarithmic size, first-order update formulas suffice for maintaining (1)
undirected reachability, and (2) directed reachability under insertions. For
classes of directed graphs for which efficient parallel algorithms can compute
non-zero circulation weights, reachability can be maintained with update
formulas that may use "modulo 2" quantifiers under changes of polylogarithmic
size. Examples for these classes include the class of planar graphs and graphs
with bounded treewidth. The latter is shown here.
  As the logics we consider cannot maintain reachability under changes of
larger sizes, our results are optimal with respect to the size of the changes.
