2 papers
cs.DC2023
Distributed derandomization revisited
Sameep Dahal, Francesco d'Amore, Henrik Lievonen +2
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves…
cs.DS2023
Distributed Half-Integral Matching and Beyond
Sameep Dahal, Jukka Suomela
By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires communication rounds, while it is possible to find a maximal fr…