Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time

Dynamic connectivity is one of the most fundamental problems in dynamic graphalgorithms. We present a randomized Las Vegas dynamic connectivity datastructure with $O(\log n(\log\log n)^2)$ amortized expected update time and$O(\log n/\log\log\log n)$ worst case query time, which comes very close to thecell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup(2011)