Smoothed Analysis for Distributed MISResearch Paper
A maximal independent set (MIS) is a basic symmetry-breaking object in distributed computing. Luby's algorithm (Luby 1986) finds one in rounds, and for decades no substantially faster algorithm for general graphs was known. Khoury and Schild (arXiv:2610.18215) showed that rounds are necessary on some graphs in the LOCAL…