18 citations · 27 across the 26 of their papers we have counts for
8 papers · 2 filters
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…