**This seminar has been *Cancelled***

**Speaker: ****Mohsen Ghaffari**, MIT

**Title:** An Improved Distributed Algorithm for Maximal Independent Set

**Abstract:**

Maximal Independent Set (MIS) is a central problem in the area of locality in distributed computing, and it is defined as follows: The network is an arbitrary n-node graph G=(V, E). Initially each node knows only its neighbors and per round, each node can send one message to each of its neighbors. The objective is to compute a maximal independent set in this model in the smallest number of rounds possible.

We present a simple randomized algorithm that computes an MIS in $O(\log Delta) + 2^{O(\sqrt{\log \log n})}$ rounds, with high probability, where $\Delta$ denotes the maximum degree in the graph. This is the first bound to achieve an optimal dependency on $\Delta$, and it improves over the celebrated O(log n) algorithm of Luby [STOC'85] and the $O(\log^2 Delta) + 2^{O(\sqrt{\log \log n})}$ algorithm of Barenboim et al. [FOCS'11]. The approach also leads to improvements in several other problems, one being local algorithms for Lovasz Local Lemma.