21 citations · 82 across the 21 of their papers we have counts for
4 papers · 1 filter
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen +5
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires communication rounds, assuming that it finds a correct assignment…
Efficient counting with optimal resilience
Christoph Lenzen, Joel Rybicki, Jukka Suomela
Consider a complete communication network of nodes, where the nodes receive a common clock pulse. We study the synchronous -counting problem: given any starting state and up…
Towards Optimal Synchronous Counting
Christoph Lenzen, Joel Rybicki, Jukka Suomela
Consider a complete communication network of nodes, where the nodes receive a common clock pulse. We study the synchronous -counting problem: given any starting state and up…
Exact bounds for distributed graph colouring
Joel Rybicki, Jukka Suomela
We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with colours, by prior work it is known t…