  In this paper, we study batch parallel algorithms for the dynamic
connectivity problem, a fundamental problem that has received considerable
attention in the sequential setting. The most well known sequential algorithm
for dynamic connectivity is the elegant level-set algorithm of Holm, de
Lichtenberg and Thorup (HDT), which achieves $O(\log^2 n)$ amortized time per
edge insertion or deletion, and $O(\log n / \log\log n)$ time per query. We
design a parallel batch-dynamic connectivity algorithm that is work-efficient
with respect to the HDT algorithm for small batch sizes, and is asymptotically
faster when the average batch size is sufficiently large. Given a sequence of
batched updates, where $\Delta$ is the average batch size of all deletions, our
algorithm achieves $O(\log n \log(1 + n / \Delta))$ expected amortized work per
edge insertion and deletion and $O(\log^3 n)$ depth w.h.p. Our algorithm
answers a batch of $k$ connectivity queries in $O(k \log(1 + n/k))$ expected
work and $O(\log n)$ depth w.h.p. To the best of our knowledge, our algorithm
is the first parallel batch-dynamic algorithm for connectivity.
