92 citations · 480 across the 54 of their papers we have counts for
5 papers · 1 filter
Algebrisation in Distributed Graph Algorithms: Fast Matrix Multiplication in the Congested Clique
Petteri Kaski, Janne H. Korhonen, Christoph Lenzen +1
While algebrisation constitutes a powerful technique in the design and analysis of centralised algorithms, to date there have been hardly any applications of algebraic techniques i…
Median Filtering is Equivalent to Sorting
Jukka Suomela
This work shows that the following problems are equivalent, both in theory and in practice: - median filtering: given an -element vector, compute the sliding window median with…
Linial's Lower Bound Made Easy
Juhana Laurinharju, Jukka Suomela
Linial's seminal result shows that any deterministic distributed algorithm that finds a -colouring of an -cycle requires at least communication rounds. We g…
Local Approximability of Minimum Dominating Set on Planar Graphs
Miikka Hilke, Christoph Lenzen, Jukka Suomela
We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a -approximation of a minimum dominating set on planar graphs,…
Large Cuts with Local Algorithms on Triangle-Free Graphs
Juho Hirvonen, Joel Rybicki, Stefan Schmid +1
We study the problem of finding large cuts in -regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 +…