Alkida Balliu

Alkida Balliu

Auto-generated profile, based on publicly available information

Alkida Balliu

Gran Sasso Science Institute, L'Aquila, Italy

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 June 2022
Verified
Conference Paper
Open access
ABAlkida Balliu
Alkida Balliu
SBSebastian Brandt
Sebastian Brandt
FKFabian Kuhn
Fabian Kuhn
DODennis Olivetti
Dennis Olivetti
We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a Δ-coloring on Δ-regular trees requires Ω(logΔn) rounds and any randomized such algorithm requires Ω(logΔlogn) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework. As a first application, we show that our Δ-coloring lower bound proof directly extends to arbdefective colorings. An arbdefective c-coloring of a graph G=(V,E) is given by a c-coloring of V and an orientation of E, where the arbdefect of a color i is the maximum number of monochromatic outgoing edges of any node of color i. We exactly characterize which variants of the arbdefective coloring problem can be solved in O(f(Δ) + log*n) rounds, for some function f, and which of them instead require Ω(logΔn) rounds for deterministic algorithms and Ω(logΔlogn) rounds for randomized ones. As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of Δ for problems that, in some sense, are much easier than Δ-coloring, as they can be solved in O(log* n) deterministic rounds in bounded-degree graphs. More specifically, we prove lower bounds as a function of Δ for a large class of distributed symmetry breaking problems, which can all be solved by a simple sequential greedy algorithm. For example, we obtain novel results for the fundamental problem of computing a (2,β)-ruling set, i.e., for computing an independent set S⊆ V such that every node v∈ V is within distance ≤ β of some node in S. We in particular show that Ω(βΔ1/β) rounds are needed even if initially an O(Δ)-coloring of the graph is given. With an initial O(Δ)-coloring, this lower bound is tight and without, it still nearly matches the existing O(βΔ2/(β+1)+log* n) upper bound. The new (2,β)-ruling set lower bound is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS ’20]. As a special case of the lower bound, we also obtain a tight linear-in-Δ lower bound for computing a maximal independent set (MIS) in trees. While such an MIS lower bound was known for general graphs, the best previous MIS lower bounds for trees was Ω(logΔ). Our lower bound even applies to a much more general family of problems that allows for almost arbitrary combinations of natural constraints from coloring problems, orientation problems, and independent set problems, and provides a single unified proof for known and new lower bound results for these types of problems. All of our lower bounds as a function of Δ also imply substantial lower bounds as a function of n. For instance, we obtain that the maximal independent set problem, on trees, requires Ω(logn / loglogn) rounds for deterministic algorithms, which is tight.

22 August 2022 in Distributed Computing
Verified
Journal Article
Open access
PDF file
ABAlkida Balliu
Alkida Balliu
SBSebastian Brandt
Sebastian Brandt
YCYi-Jun Chang
Yi-Jun Chang
DODennis Olivetti
Dennis Olivetti
JSJan Studený
Jan Studený
ATAleksandr Tereshchenko
Aleksandr Tereshchenko
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 $$ x ∈ Σ we specify what are permitted label combinations of the children for an internal node of label x (the leaf nodes are unconstrained). This formalism is expressive enough to capture many classic problems studied in distributed computing, including vertex coloring, edge coloring, and maximal independent set. We show that the distributed computational complexity of any such problem $$\Pi $$ Π falls in one of the following classes: it is O(1), $$\Theta (\log ^* n)$$ Θ ( log ∗ n ) , $$\Theta (\log n)$$ Θ ( log n ) , or $$n^{\Theta (1)}$$ n Θ ( 1 ) rounds in trees with n nodes (and all of these classes are nonempty). We show that the complexity of any given problem is the same in all four standard models of distributed graph algorithms: deterministic $$\mathsf {LOCAL}$$ LOCAL , randomized $$\mathsf {LOCAL}$$ LOCAL , deterministic $$\mathsf {CONGEST}$$ CONGEST , and randomized $$\mathsf {CONGEST}$$ CONGEST model. In particular, we show that randomness does not help in this setting, and the complexity class $$\Theta (\log \log n)$$ Θ ( log log n ) does not exist (while it does exist in the broader setting of general trees). We also show how to systematically determine the complexity class of any such problem $$\Pi $$ Π , i.e., whether $$\Pi $$ Π takes O(1), $$\Theta (\log ^* n)$$ Θ ( log ∗ n ) , $$\Theta (\log n)$$ Θ ( log n ) , or $$n^{\Theta (1)}$$ n Θ ( 1 ) rounds. While the algorithm may take exponential time in the size of the description of $$\Pi $$ Π , it is nevertheless practical: we provide a freely available implementation of the classifier algorithm, and it is fast enough to classify many problems of interest.

15 June 2025
Verified
Conference Paper
Open access
ABAlkida Balliu
Alkida Balliu
SBSebastian Brandt
Sebastian Brandt
XCXavier Coiteux-Roy
Xavier Coiteux-Roy
FDFrancesco D'AMore
Francesco D'AMore
MEMassimo Equi
Massimo Equi
IVIsadora Veeren
Isadora Veeren

17 June 2024
Verified
Conference Paper
Open access
ABAlkida Balliu
Alkida Balliu
TBThomas Boudier
Thomas Boudier
SBSebastian Brandt
Sebastian Brandt
DODennis Olivetti
Dennis Olivetti
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 common such setting, known as the Supported LOCAL model, where the input graph---on which the studied graph problem has to be solved---is guaranteed to be a subgraph of the underlying communication network. Building on a successful lower bound technique for the LOCAL model called round elimination, we develop a framework for proving complexity lower bounds in the stronger Supported LOCAL model. Our framework reduces the task of proving a (deterministic or randomized) lower bound for a given problem Π to the graph-theoretic task of proving non-existence of a solution to another problem Π′ (on a suitable graph) that can be derived from Π in a mechanical manner. We use the developed framework to obtain substantial---and, in the majority of cases, asymptotically tight---Supported LOCAL lower bounds for a variety of fundamental graph problems, including maximal matching, maximal independent set, ruling sets, arbdefective colorings, and generalizations thereof. In a nutshell, for essentially any major lower bound proved in the LOCAL model in recent years, we prove a similar lower bound in the Supported LOCAL model. Our framework also gives rise to a new deterministic version of round elimination in the LOCAL model: while, previous to our work, the general round elimination technique required the use of randomness (even for obtaining deterministic lower bounds), our framework allows to obtain deterministic (and therefore via known lifting techniques also randomized) lower bounds in a purely deterministic manner. Previously, such a purely deterministic application of round elimination was only known for the specific problem of sinkless orientation [SOSA'23].

25 June 2022
Verified
Book Chapter
Closed access
PDF file
ABAlkida Balliu
Alkida Balliu
JHJuho Hirvonen
Juho Hirvonen
DMDarya Melnyk
Darya Melnyk
DODennis Olivetti
Dennis Olivetti
JRJoel Rybicki
Joel Rybicki
JSJukka Suomela
Jukka Suomela

5 July 2023 in Distributed Computing
Verified
Journal Article
Open access
PDF file
ABAlkida Balliu
Alkida Balliu
MGMohsen Ghaffari
Mohsen Ghaffari
FKFabian Kuhn
Fabian Kuhn
DODennis Olivetti
Dennis Olivetti
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 which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) in n-node graphs of maximum degree \(\Delta \) is at least \(\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )\). This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM’16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also \(\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )\)—this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an \(O(\sqrt{\log \log n})\) factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity to O(1). For maximal matching, we show that while the randomized node-averaged complexity is \(\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )\), the randomized edge-averaged complexity is O(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is \(O(\log ^2\Delta + \log ^* n)\) and the deterministic node-averaged complexity of maximal matching is \(O(\log ^3\Delta + \log ^* n)\). Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be \(\Theta (\log n)\), even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity \(O(\log ^* n)\), while keeping the worst-case complexity in \(O(\log n)\).