18 citations · 22 across the 23 of their papers we have counts for
45 papers
Distributed Lower Bounds via Automatic Self-Reduction
Alkida Balliu, Francesco d'Amore, Dennis Olivetti
The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distribu…
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +3
One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model u…
On the Universality of Round Elimination Fixed Points
Alkida Balliu, Sebastian Brandt, Ole Gabsdil +2
Recent work on distributed graph algorithms [e.g. STOC 2022, ITCS 2022, PODC 2020] has drawn attention to the following open question: are round elimination fixed points a universa…
New Hardness Results for the LOCAL Model via a Simple Self-Reduction
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +1
Very recently, Khoury and Schild [FOCS 2025] showed that any randomized LOCAL algorithm that solves maximal matching requires rounds, where is the…
Distributed Algorithms for Potential Problems
Alkida Balliu, Thomas Boudier, Francesco d'Amore +4
In this work, we present a fast distributed algorithm for local potential problems: these are graph problems where the task is to find a locally optimal solution where no node can…
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Alkida Balliu, Corinna Coupette, Antonio Cruciani +6
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no d…