Showing 2025Show all
3 papers · 1 filter
cs.DC2025
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…
cs.DC2025
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…
cs.DC2025
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…