# Mohsen Ghaffari: An Improved Distributed Algorithm for Maximal Independent Set

Friday, September 18, 2015 - 1:00pm to 2:30pm
Location:
32-G631
Speaker:
Mohsen Ghaffari
Biography:
MIT

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.