47 citations · 107 across the 20 of their papers we have counts for
28 papers
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…
Fast, Fair and Truthful Distributed Stable Matching for Common Preferences
Juho Hirvonen, Sara Ranjbaran
Stable matching is a fundamental problem studied both in economics and computer science. The task is to find a matching between two sides of agents that have preferences over who t…
Intuitive method for constructing effective field theories
J. Hirvonen
We derive a novel method for constructing effective field theories. Physically, the method is very close to the intuition behind effective field theories: One can integrate out the…
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…
Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory
Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee +1
Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They…
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…
On the Feasibility of Perfect Resilience with Local Fast Failover
Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet +2
In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover.…
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…
Improved Distributed -Coloring
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn +1
We present a randomized distributed algorithm that computes a -coloring in any non-complete graph with maximum degree in rounds,…
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…
Non-Local Probes Do Not Help with Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi +2
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computi…
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…