MIS in the Congested Clique Model in $O$ Rounds.

We give a maximal independent set (MIS) algorithm that runs in $O(\log \log\Delta)$ rounds in the congested clique model, where $\Delta$ is the maximumdegree of the input graph. This improves upon the $O(\frac{\log(\Delta) \cdot\log \log \Delta}{\sqrt{\log n}} + \log \log \Delta )$ rounds algorithm of[Ghaffari, PODC '17], where $n$ is the number of vertices of the input graph.

In the first stage of our algorithm, we simulate the first$O(\frac{n}{\text{poly} \log n})$ iterations of the sequential random orderGreedy algorithm for MIS in the congested clique model in $O(\log \log \Delta)$rounds. This thins out the input graph relatively quickly: After this stage,the maximum degree of the residual graph is poly-logarithmic. In the secondstage, we run the MIS algorithm of [Ghaffari, PODC '17] on the residual graph,which completes in $O(\log \log \Delta)$ rounds on graphs of poly-logarithmicdegree.