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…
Distributed Quantum Advantage in Locally Checkable Labeling Problems
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +6
In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL model of distribut…
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti +1
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as -colo…
Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prio…
Towards Fully Automatic Distributed Lower Bounds
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
In the past few years, a successful line of research has lead to lower bounds for several fundamental local graph problems in the distributed setting. These results were obtained v…
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette +2
We revisit asynchronous computing in networks of crash-prone processes, under the asynchronous variant of the standard LOCAL model, recently introduced by Fraigniaud et al. [DISC 2…
Shared Randomness Helps with Local Distributed Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +5
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is loca…
Completing the Node-Averaged Complexity Landscape of LCLs on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of res…
Distributed Computation with Local Advice
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +4
In this work we study local computation with advice: the goal is to solve a graph problem with a distributed algorithm in communication rounds, for some function tha…
Tight Lower Bounds in the Supported LOCAL Model
Alkida Balliu, Thomas Boudier, Sebastian Brandt +1
We study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start…
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminati…
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi +2
A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with i…
Optimal Deterministic Massively Parallel Connectivity on Forests
Alkida Balliu, Rustam Latypov, Yannic Maus +2
We show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent b…
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph …
Exponential Speedup Over Locality in MPC with Optimal Memory
Alkida Balliu, Sebastian Brandt, Manuela Fischer +4
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example p…
Node and Edge Averaged Complexities of Local Graph Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +1
The node-averaged complexity of a distributed algorithm running on a graph is the average over the times at which the nodes of finish their computation and commit…
Distributed Edge Coloring in Time Polylogarithmic in
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main resu…
Efficient Classification of Locally Checkable Problems in Regular Trees
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)…
Improved Distributed Fractional Coloring Algorithms
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
We prove new bounds on the distributed fractional coloring problem in the LOCAL model. Fractional -colorings can be understood as multicolorings as follows. For some natural num…