  We present a randomized algorithm for dynamic graph connectivity. With
failure probability less than $1/n^c$ (for any constant $c$ we choose), our
solution has worst case running time $O(\log^3 n)$ per edge insertion,
$O(\log^4 n)$ per edge deletion, and $O(\log n/\log\log n)$ per query, where
$n$ is the number of vertices. The previous best algorithm has worst case
running time $O(\log^4 n)$ per edge insertion and $O(\log^5 n)$ per edge
deletion. The improvement is made by reducing the randomness used in the
previous result, so that we save a $\log n$ factor in update time.
  Specifically, \cite{kapron2013dynamic} uses $\log n$ copies of a data
structure in order to boost a success probability from $1/2$ to $1-n^{-c}$. We
show that, in fact though, because of the special structure of their algorithm,
this boosting via repetition is unnecessary. Rather, we can still obtain the
same correctness guarantee with high probability by arguing via a new
invariant, without repetition.
