Optimal Dynamic Distributed MIS

23/05/2017 - 14:00 - 15:00

Abstract: 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. This holds for all changes: edge- and node- insertions and removals, gracefully and abruptly. 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

Keren Censor-Hillel
דוא"ל להרשמה: 
Computer Science Department, Technion I.I.T
BIU Engineering Building 1103, Room 329