  We present the first algorithm for maintaining a maximal independent set
(MIS) of a fully dynamic graph---which undergoes both edge insertions and
deletions---in polylogarithmic time. Our algorithm is randomized and, per
update, takes $O(\log^2 \Delta \cdot \log^2 n)$ expected time. Furthermore, the
algorithm can be adjusted to have $O(\log^2 \Delta \cdot \log^4 n)$ worst-case
update-time with high probability. Here, $n$ denotes the number of vertices and
$\Delta$ is the maximum degree in the graph.
  The MIS problem in fully dynamic graphs has attracted significant attention
after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18]
who presented an algorithm with $O(m^{3/4})$ update-time (and thus broke the
natural $\Omega(m)$ barrier) where $m$ denotes the number of edges in the
graph. This result was improved in a series of subsequent papers, though, the
update-time remained polynomial. In particular, the fastest algorithm prior to
our work had $\widetilde{O}(\min\{\sqrt{n}, m^{1/3}\})$ update-time [Assadi et
al. SODA'19].
  Our algorithm maintains the lexicographically first MIS over a random order
of the vertices. As a result, the same algorithm also maintains a
3-approximation of correlation clustering. We also show that a simpler variant
of our algorithm can be used to maintain a random-order lexicographically first
maximal matching in the same update-time.
