Alkida Balliu
YOU?
Author Swipe
View article: Distributed Algorithms for Potential Problems
Distributed Algorithms for Potential Problems Open
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 unilaterally improve the utility in its local neighborhood b…
View article: Distributed Quantum Advantage for Local Problems
Distributed Quantum Advantage for Local Problems Open
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 prior work, such a separation was known only for an artificial …
View article: Distributed Quantum Advantage in Locally Checkable Labeling Problems
Distributed Quantum Advantage in Locally Checkable Labeling Problems Open
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 distributed computing: our problem can be solved in $O(\log n)$ comm…
View article: Exponential speedup over locality in MPC with optimal memory
Exponential speedup over locality in MPC with optimal memory Open
Locally Checkable Labeling () problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal indepe…
View article: Distributed Computation with Local Advice
Distributed Computation with Local Advice Open
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph p…
View article: Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost Open
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 $(Δ+1)$-coloring and maximal independent set. It is known from previous…
View article: Towards Fully Automatic Distributed Lower Bounds
Towards Fully Automatic Distributed Lower Bounds Open
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 via a technique called round elimination. On a high level, t…
View article: Shared Randomness Helps with Local Distributed Problems
Shared Randomness Helps with Local Distributed Problems Open
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 locally checkable labeling problems (LCLs), introduced by Naor …
View article: Tight Lower Bounds in the Supported LOCAL Model
Tight Lower Bounds in the Supported LOCAL Model Open
In this work, 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 of the computation. We focus on the most com…
View article: Brief Announcement: Local Advice and Local Decompression
Brief Announcement: Local Advice and Local Decompression Open
In this work we study local computation with advice: the goal is to solve a graph problem $\Pi$ with a distributed algorithm in $f(\Delta)$ communication rounds, for some function $f$ that only depends on the maximum degree $\Delta$ of the…
View article: Completing the Node-Averaged Complexity Landscape of LCLs on Trees
Completing the Node-Averaged Complexity Landscape of LCLs on Trees Open
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 research with regards to this new complexity measure is to und…
View article: Completing the Node-Averaged Complexity Landscape of LCLs on Trees
Completing the Node-Averaged Complexity Landscape of LCLs on Trees Open
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 research with regards to this new complexity measure is to und…
View article: Tight Lower Bounds in the Supported LOCAL Model
Tight Lower Bounds in the Supported LOCAL Model Open
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 of the computation. We focus on the most common such setti…
View article: Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs Open
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 2022]. We focus on the vertex coloring problem, and our cont…
View article: On the Node-Averaged Complexity of Locally Checkable Problems on Trees
On the Node-Averaged Complexity of Locally Checkable Problems on Trees Open
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, culminating in an almost-complete classification on general graphs a…
View article: Node and edge averaged complexities of local graph problems
Node and edge averaged complexities of local graph problems Open
We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph $$G=(V,E)$$ is the average over …
View article: A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs Open
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 increasing edge time labels. We consider the problem of assi…
View article: Optimal Deterministic Massively Parallel Connectivity on Forests
Optimal Deterministic Massively Parallel Connectivity on Forests Open
Publisher Copyright: Copyright © 2023 by SIAM.
View article: Sinkless Orientation Made Simple
Sinkless Orientation Made Simple Open
International audience
View article: Locally Checkable Problems in Rooted Trees
Locally Checkable Problems in Rooted Trees Open
Consider any locally checkable labeling problem Π in rooted regular trees: there is a finite set of labels Σ, and for each label x ∈ Σ we specify what are permitted label combinations of the children for an internal node of label x (the le…
View article: Optimal Deterministic Massively Parallel Connectivity on Forests
Optimal Deterministic Massively Parallel Connectivity on Forests Open
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 breakthrough result by Coy and Czumaj [STOC'22] shows that, …
View article: Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs Open
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 $H=(V_H,E_H)$ is a maximal disjoint set $M\subseteq E_H$ of hyperedges an…
View article: Locally checkable problems in rooted trees
Locally checkable problems in rooted trees Open
Consider any locally checkable labeling problem $$\Pi $$ in rooted regular trees : there is a finite set of labels $$\Sigma $$ , and for each label $$x \in \Sigma $$ we specify what are permitted label combinations of the children…
View article: Exponential Speedup Over Locality in MPC with Optimal Memory
Exponential Speedup Over Locality in MPC with Optimal Memory Open
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 problems in this class include maximal matching, maximal ind…
View article: Node and Edge Averaged Complexities of Local Graph Problems
Node and Edge Averaged Complexities of Local Graph Problems Open
The node-averaged complexity of a distributed algorithm running on a graph $G=(V,E)$ is the average over the times at which the nodes $V$ of $G$ finish their computation and commit to their outputs. We study the node-averaged complexity fo…
View article: Node and Edge Averaged Complexities of Local Graph Problems
Node and Edge Averaged Complexities of Local Graph Problems Open
We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph G=(V,E) is the average over the times at …
View article: Distributed Edge Coloring in Time Polylogarithmic in Δ
Distributed Edge Coloring in Time Polylogarithmic in Δ Open
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 result, we show that a (2Δ-1)-edge coloring can be computed in …
View article: Distributed Edge Coloring in Time Polylogarithmic in $Δ$
Distributed Edge Coloring in Time Polylogarithmic in $Δ$ Open
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 result, we show that a $(2Δ-1)$-edge coloring can be computed i…