Juho Hirvonen received his doctorate from Aalto University in 2016, after which he was a postdoctoral researcher at the IRIF research institute at the University Paris Diderot, and the University of Freiburg. He was an Academy of Finland Postdoctoral Researcher, and is currently an HIIT Research Fellow at Aalto University.
His current research is about building an interdisciplinary connection between distributed computing and game theory: How hardness of distributed computation limits strategic behaviour, and how distributed algorithms can be used as building blocks in mechanism design. Dr. Hirvonen’s previous research has been about the theory of distributed computing, and in particular impossibility results: For example, their team received the best paper award at the IEEE Symposium on Foundations of Computing in 2019 for proving new impossibility results for maximal matching and maximal independent set.
Recent publications and manuscripts:
Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid: Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory. Submitted for publication. https://arxiv.org/abs/2102.13457
In this work we show that Nash equilibria of graphical games (games on networks) as computational problems are studied in distributed computing. We use this connection to analyse various graphical games, implying different convergence behaviour among them.
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela: Lower Bounds for Maximal Matchings and Maximal Independent Sets. J. ACM 68(5), 2021.
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela: Lower Bounds for Maximal Matchings and Maximal Independent Sets. FOCS 2019. (Best paper award).
We show that the locality (measure of how far information has to travel in a distributed system in order to solve a given problem) of maximal matching (and maximal independent set) is Omega(Delta), where Delta is the maximum degree of the input network. This is tight: it matches the locality of existing algorithms. We use the so-called round elimination technique that we have developed to prove this.
Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, Jukka Suomela: Local Mending. SIROCCO 2022.
We establish a locality measure for the hardness of mending a partial solution. We study the complexity landscape of this measure: how hard mending can be and how is it related to the hardness of solving the corresponding problem from scratch in the distributed setting.