4 papers
No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model
Seri Khoury, Aaron Schild
We prove that -round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the…
On the Randomized Locality of Matching Problems in Regular Graphs
Seri Khoury, Manish Purohit, Aaron Schild +1
The main goal in distributed symmetry-breaking is to understand the locality of problems; i.e., the radius of the neighborhood that a node needs to explore in order to arrive at it…
Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
Seri Khoury, Aaron Schild
In this work, we present an lower bound for Maximal Matching (MM) in -ary trees against randomized algorithms. By a folklore reduct…
Breaking Barriers for Distributed MIS by Faster Degree Reduction
Seri Khoury, Aaron Schild
We study the problem of finding a maximal independent set (MIS) in the standard LOCAL model of distributed computing. Classical algorithms by Luby [JACM'86] and Alon, Babai, and It…