47 citations · 107 across the 20 of their papers we have counts for
22 papers · 1 filter
Designing Local Distributed Mechanisms
Juho Hirvonen, Sara Ranjbaran
In this work we introduce a new notion: local mechanisms. These are truthful mechanisms that have an implementation as fast distributed algorithms and non-trivial approximation gua…
On the Price of Locality in Static Fast Rerouting
Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet +2
Modern communication networks feature fully decentralized flow rerouting mechanisms which allow them to quickly react to link failures. This paper revisits the fundamental algorith…
Sparse Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Juho Hirvonen, Janne H. Korhonen +2
We study matrix multiplication in the low-bandwidth model: There are computers, and we need to compute the product of two matrices. Initially computer knows ro…
Local Mending
Alkida Balliu, Juho Hirvonen, Darya Melnyk +3
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far o…
Classification of distributed binary labeling problems
Alkida Balliu, Sebastian Brandt, Yuval Efron +4
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable…
Locality of not-so-weak coloring
Alkida Balliu, Juho Hirvonen, Christoph Lenzen +2
Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally…
Lower bounds for maximal matchings and maximal independent sets
Alkida Balliu, Sebastian Brandt, Juho Hirvonen +3
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in communication rounds; here is the number of nodes and …
On the Power of Preprocessing in Decentralized Network Optimization
Klaus-Tycho Foerster, Juho Hirvonen, Stefan Schmid +1
As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to…
Hardness of minimal symmetry breaking in distributed computing
Alkida Balliu, Juho Hirvonen, Dennis Olivetti +1
A graph is weakly -colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we…
Local verification of global proofs
Laurent Feuilloley, Juho Hirvonen
In this work we study the cost of local and global proofs on distributed verification. In this setting the nodes of a distributed system are provided with a nondeterministic proof…
Redundancy in Distributed Proofs
Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen +2
Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on…
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…
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…
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…
A hierarchy of local decision
Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen
We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by…
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…
Node Labels in Local Decision
Pierre Fraigniaud, Juho Hirvonen, Jukka Suomela
The role of unique node identifiers in network computing is well understood as far as symmetry breaking is concerned. However, the unique identifiers also leak information about th…
Locally Optimal Load Balancing
Laurent Feuilloley, Juho Hirvonen, Jukka Suomela
This work studies distributed algorithms for locally optimal load-balancing: We are given a graph of maximum degree , and each node has up to units of load. The task is to d…
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 +…
Linear-in- Lower Bounds in the LOCAL Model
Mika Göös, Juho Hirvonen, Jukka Suomela
By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in rounds, where is the maximum degree of the graph. We s…
Lower Bounds for Local Approximation
Mika Göös, Juho Hirvonen, Jukka Suomela
In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique -bit identifier. We prove that for a general class of graph probl…
Distributed Maximal Matching: Greedy is Optimal
Juho Hirvonen, Jukka Suomela
We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with colours, there is a trivial greedy al…