  In the fully dynamic maximal independent set (MIS) problem our goal is to
maintain an MIS in a given graph $G$ while edges are inserted and deleted from
the graph. The first non-trivial algorithm for this problem was presented by
Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic
fully dynamic MIS with $O(m^{3/4})$ update time. Later, this was independently
improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to
$\tilde{O}(m^{2/3})$ update time. Du and Zhang [arXiv 2018] also presented a
randomized algorithm against an oblivious adversary with $\tilde{O}(\sqrt{m})$
update time.
  The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA
2019] who obtained randomized algorithms against oblivious adversary with
$\tilde{O}(\sqrt{n})$ and $\tilde{O}(m^{1/3})$ update times.
  In this paper, we propose a dynamic randomized algorithm against oblivious
adversary with expected worst-case update time of $O(\log^4n)$. As a direct
corollary, one can apply the black-box reduction from a recent work by
Bernstein, Forster, and Henzinger [SODA 2019] to achieve $O(\log^6n)$
worst-case update time with high probability. This is the first dynamic MIS
algorithm with very fast update time of poly-log.
