92 citations · 480 across the 54 of their papers we have counts for
6 papers · 1 filter
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen +3
A number of recent papers -- e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) -- have…
Distributed Colour Reduction Revisited
Jukka Kohonen, Janne H. Korhonen, Christopher Purcell +2
We give a new, simple distributed algorithm for graph colouring in paths and cycles. Our algorithm is fast and self-contained, it does not need any globally consistent orientation,…
Improved Distributed Degree Splitting and Edge Coloring
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn +3
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discre…
Constant Space and Non-Constant Time in Distributed Computing
Tuomo Lempiäinen, Jukka Suomela
While the relationship of time and space is an established topic in traditional centralised complexity theory, this is not the case in distributed computing. We aim to remedy this…
Towards a complexity theory for the congested clique
Janne H. Korhonen, Jukka Suomela
The congested clique model of distributed computing has been receiving attention as a model for densely connected distributed systems. While there has been significant progress on…
LCL problems on grids
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen +6
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cy…