Alkida Balliu

STOC Conference 2025 Conference Paper

Distributed Quantum Advantage for Local Problems

• Alkida Balliu
• Sebastian Brandt 0002
• Xavier Coiteux-Roy
• Francesco d'Amore 0001
• Massimo Equi
• François Le Gall
• Henrik Lievonen
• Augusto Modanese

SODA Conference 2023 Conference Paper

Distributed Maximal Matching and Maximal Independent Set on Hypergraphs

• Alkida Balliu
• Sebastian Brandt 0002
• Fabian Kuhn
• Dennis Olivetti

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 ⊆ E h of hyperedges and an MIS S ⊆ V H is a maximal set of nodes such that no hyperedge is fully contained in S. Both problems can be solved by a simple sequential greedy algorithm, which can be implemented naïvely in O (Δ r + log * n ) rounds, where Δ is the maximum degree, r is the rank, and n is the number of nodes of the hypergraph. We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires Ω(min {Δ r, log Δr n }) rounds, and any randomized one requires Ω(min {Δ r, log Δ r log n }) rounds. Hence, for any algorithm with a complexity of the form O ( f (Δ, r ) + g ( n )), we have f (Δ, r ) ∈ Ω(Δ r ) if g(n) is not too large, and in particular if g(n) = log * n (which is the optimal asymptotic dependency on n due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on the round elimination framework, and its structure is inspired by a new round elimination fixed point that we give for the Δ-vertex coloring problem in hypergraphs, where nodes need to be colored such that there are no monochromatic hyperedges. For the MIS problem on hypergraphs, we show that for Δ ≪ r, there are significant improvements over the naive O (Δ r + log * n )-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in O (Δ 2 · log r + Δ · log r · log * r + log * n ) rounds. We further show that at the cost of a much worse dependency on Δ, the dependency on r can be removed almost entirely, by giving an algorithm with round complexity Δ O (Δ) · log * r + 0(log * n ).

SODA Conference 2023 Conference Paper

Optimal Deterministic Massively Parallel Connectivity on Forests

• Alkida Balliu
• Rustam Latypov
• Yannic Maus
• Dennis Olivetti
• Jara Uitto

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, in this setting, it is possible to deterministically identify connected components on graphs in O (log D + log log n ) rounds, where D is the diameter of the graph and n the number of nodes. The authors left open a major question: is it possible to get rid of the additive log log n factor and deterministically identify connected components in a runtime that is completely independent of n? We answer the above question in the affirmative in the case of forests. We give an algorithm that identifies connected components in O (log D ) deterministic rounds. The total memory required is O(n + m ) words, where m is the number of edges in the input graph, which is optimal as it is only enough to store the input graph. We complement our upper bound results by showing that Ω(log D ) time is necessary even for component-unstable algorithms, conditioned on the widely believed 1 vs. 2 cycles conjecture. Our techniques also yield a deterministic forest-rooting algorithm with the same runtime and memory bounds. Furthermore, we consider Locally Checkable Labeling problems (LCLs), whose solution can be verified by checking the O (1)-radius neighborhood of each node. We show that any LCL problem on forests can be solved in O (log D ) rounds with a canonical deterministic algorithm, improving over the O (log n ) runtime of Brandt, Latypov and Uitto [DISC'21]. We also show that there is no algorithm that solves all LCL problems on trees asymptotically faster. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 03530

STOC Conference 2022 Conference Paper

Distributed ∆-coloring plays hide-and-seek

• Alkida Balliu
• Sebastian Brandt 0002
• Fabian Kuhn
• 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 Δ log n ) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework.

AIJ Journal 2022 Journal Article

On Pareto optimality in social distance games

• Alkida Balliu
• Michele Flammini
• Giovanna Melideo
• Dennis Olivetti

We investigate Pareto stability in Social Distance Games ( SDG s), which are coalition formation games where agents utilities are proportional to their harmonic centralities in the respective coalitions, i. e. , to the average inverse distance from the other agents. Pareto optimal solutions have already been considered in the literature as outcomes arising from the strategic interaction of the self-interested agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. First, by providing a polynomial-time reduction from the NP-complete Restricted Exact 3-Cover by 3-Sets problem, we prove that computing a Pareto stable solution for a SDG maximizing the social welfare is NP-hard also in bounded degree graphs. Then, we show that a 2 min ⁡ ( Δ, n ) -approximating solution can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. Moreover, we provide asymptotically tight bounds on the price of Pareto optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed arcs, unweighted and weighted arcs.

FOCS Conference 2020 Conference Paper

Distributed Lower Bounds for Ruling Sets

• Alkida Balliu
• Sebastian Brandt 0002
• Dennis Olivetti

Given a graph G=(V, E), an ( α, β) -ruling set is a subset S ⊆ V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most β. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a ( 2, β) - ruling set (and hence also any ( α, β) -ruling set with ) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Δ the maximum degree, and c is some universal constant independent of n and Δ. · Any deterministic algorithm requires Ω(min{[(logΔ)/(β log log Δ)], log Δ n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log Δ n}. By optimizing Δ, this implies a deterministic lower bound of Ω(√{[log n/(β log log n)]}) for all β ≤ c 3 √{[log n/log log n]}. ·Any randomized algorithm requires Ω(min{[(log Δ)/(β log log Δ)], log log n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log log n}. By optimizing Δ, this implies a randomized lower bound of Ω(√{[log log n/(βlog log log n)]}) for all β ≤ c 3 √{[log log n/log log log n]}. For, this improves on the previously best lower bound of Ω(log*n) rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J. Disc. Math. '91] (resp. Ω(1) rounds if β ∈ ω(log*n)). For β = 1, i. e. , for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Ω(log*n) on trees, as our bounds already hold on trees.

FOCS Conference 2019 Conference Paper

Lower Bounds for Maximal Matchings and Maximal Independent Sets

• Alkida Balliu
• Sebastian Brandt 0002
• Juho Hirvonen
• Dennis Olivetti
• Mikaël Rabie
• Jukka Suomela

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log^* n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Δ + log log n / log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Δ + log n / log log n) rounds; this is an improvement over prior lower bounds also as a function of n.

JAIR Journal 2019 Journal Article

On Non-Cooperativeness in Social Distance Games

• Alkida Balliu
• Michele Flammini
• Giovanna Melideo
• Dennis Olivetti

We consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 6/5 − ε, for any ε > 0. Finally, we characterize the price of stability 5 of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.

STOC Conference 2018 Conference Paper

New classes of distributed time complexity

• Alkida Balliu
• Juho Hirvonen
• Janne H. Korhonen
• Tuomo Lempiäinen
• Dennis Olivetti
• Jukka Suomela

A number of recent papers – e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) – have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem Π in which a solution can be verified by checking all radius- O (1) neighbourhoods, and the question is what is the smallest T such that a solution can be computed so that each node chooses its own output based on its radius- T neighbourhood. Here T is the distributed time complexity of Π. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are Θ(1), Θ(log * n ), Θ(log n ), Θ( n 1/ k ), and Θ( n ). It is also known that there are two gaps: one between ω(1) and o (loglog * n ), and another between ω(log * n ) and o (log n ). It has been conjectured that many more gaps exist, and that the overall time hierarchy is relatively simple – indeed, this is known to be the case in restricted graph families such as cycles and grids. We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including Θ(log α n ) for any α ≥ 1, 2 Θ(log α n ) for any α ≤ 1, and Θ( n α ) for any α < 1/2 in the high end of the complexity spectrum, and Θ(log α log * n ) for any α ≥ 1, 2 Θ(log α log * n ) for any α ≤ 1, and Θ((log * n ) α ) for any α ≤ 1 in the low end of the complexity spectrum; here α is a positive rational number.

AAAI Conference 2017 Conference Paper

Nash Stability in Social Distance Games

• Alkida Balliu
• Michele Flammini
• Giovanna Melideo
• Dennis Olivetti

We consider Social Distance Games (SDGs), that is cluster formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions, i. e. , to the average inverse distance from the other agents. We adopt Nash stable outcomes, that is states in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although SDGs always admit a Nash equilibrium, we prove that it is NP-hard to find a social welfare maximizing one and obtain a negative result concerning the game convergence. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph, and a lower bound on the price of stability of 6/5 −. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5.

AAAI Conference 2017 Conference Paper

On Pareto Optimality in Social Distance Games

• Alkida Balliu
• Michele Flammini
• Dennis Olivetti

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i. e. , to the average inverse distance from the other agents. Pareto optimal solutions have been already considered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ, √ n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.