Mohsen Ghaffari: An Improved Distributed Algorithm for Maximal Independent Set

We are all familiar with Luby's seminal MIS algorithm which has a round complexity of O(log n). In this talk, I will describe a different MIS algorithm, which improves the bound to O(log Delta) + 2^{\sqrt{log log n}}. The algorithm furthermore exhibits many interesting characteristics and has several implications.