Event № 248
I will describe how we can exploit the locality of a maximal independent set (MIS) to the extreme, by showing how to update an MIS in a dynamic distributed setting within only a single adjustment in expectation. The approach is surprisingly simple and is based on a novel analysis of the sequential random greedy algorithm.
No background in distributed computing will be assumed. The talk is based on joint work with Elad Haramaty and Zohar Karnin.