Aaltodoc Repository :: Browsing by Author "Balliu, Alkida"

Browsing by Author "Balliu, Alkida"

Now showing 1 - 17 of 17

Almost global problems in the LOCAL model
(Springer Verlag, 2021-08) Balliu, Alkida; Brandt, Sebastian; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.; Computer Science Professors; Computer Science - Large-scale Computing and Data Analysis (LSCA); Computer Science - Algorithms and Theoretical Computer Science (TCS); Swiss Federal Institute of Technology Zurich
The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges:There are lots of problems with time complexities of Θ(log ∗n) or Θ(log n).It is not possible to have a problem with complexity between ω(log ∗n) and o(log n).In general graphs, we can construct LCL problems with infinitely many complexities between ω(log n) and no(1).In trees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are LCL problems with complexities of the form Θ(nα) for any rational 0 < α≤ 1 / 2 , while for trees only complexities of the form Θ(n1/k) are known. No LCL problem with complexity between ω(n) and o(n) is known, and neither are there results that would show that such problems do not exist. We show that:In general graphs, we can construct LCL problems with infinitely many complexities between ω(n) and o(n).In trees, problems with such complexities do not exist. Put otherwise, we show that any LCL with a complexity o(n) can be solved in time O(n) in trees, while the same is not true in general graphs.
Almost global problems in the LOCAL model
(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2018) Balliu, Alkida; Brandt, Sebastian; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.; Swiss Federal Institute of Technology Zurich
The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges: - There are lots of problems with time complexities Theta(log^* n) or Theta(log n). - It is not possible to have a problem with complexity between omega(log^* n) and o(log n). - In general graphs, we can construct LCL problems with infinitely many complexities between omega(log n) and n^{o(1)}. - In trees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are problems with complexities of the form Theta(n^alpha) for any rational 0 < alpha <=1/2, while for trees only complexities of the form Theta(n^{1/k}) are known. No LCL problem with complexity between omega(sqrt{n}) and o(n) is known, and neither are there results that would show that such problems do not exist. We show that: - In general graphs, we can construct LCL problems with infinitely many complexities between omega(sqrt{n}) and o(n). - In trees, problems with such complexities do not exist. Put otherwise, we show that any LCL with a complexity o(n) can be solved in time O(sqrt{n}) in trees, while the same is not true in general graphs.
Brief Announcement: Classification of Distributed Binary Labeling Problems
(2020-07-31) Balliu, Alkida; Brandt, Sebastian; Efron, Yuval; Hirvonen, Juho; Maus, Yannic; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.; Computer Science - Algorithms and Theoretical Computer Science (TCS); ETH Zurich; Technion - Israel Institute of Technology; University of Freiburg
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.
Brief Announcement: Local Advice and Local Decompression
(2024-06-17) Balliu, Alkida; Brandt, Sebastian; Kuhn, Fabian; Nowicki, Krzysztof; Olivetti, Dennis; Rotenberg, Eva; Suomela, Jukka; Department of Computer Science; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA); Professorship Suomela J.; Helmholtz Center for Information Security; University of Freiburg; Pathway.com; Danmarks Tekniske Universitet; Gran Sasso Science Institute
In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in f (Δ) communication rounds, for some function f that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Our main results are: (1) Any locally checkable labeling problem (LCL) can be solved in graphs with sub-exponential growth with only 1 bit of advice per node. Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. (2) The assumption of sub-exponential growth is necessary: assuming the Exponential-Time Hypothesis (ETH), there are LCLs that cannot be solved in general with any constant number of bits per node. (3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. (4) As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in f(Δ) rounds. (5) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. (6) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. Here, it remains open whether we can make the advice arbitrarily sparse.
Classification of Distributed Binary Labeling Problems
(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2020) Balliu, Alkida; Sebastian, Brandt; Efron, Yuval; Hirvonen, Juho; Maus, Yannic; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Attiya, Hagit; Professorship Suomela J.; Computer Science - Algorithms and Theoretical Computer Science (TCS); Swiss Federal Institute of Technology Zurich; Technion - Israel Institute of Technology; Albert-Ludwigs-Universität Freiburg
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity Θ(log^* n), and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.
Distributed Half-Integral Matching and Beyond
(Springer, 2023) Dahal, Sameep; Suomela, Jukka; Department of Computer Science; Rajsbaum, Sergio; Balliu, Alkida; Olivetti, Dennis; Daymude, Joshua J.; Computer Science Professors; Computer Science - Large-scale Computing and Data Analysis (LSCA); Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Suomela J.; Department of Computer Science
By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Ω(log∗n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0,12,1}. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Δ=2d, and any distributed graph algorithm with round complexity T(Δ) that only depends on Δ and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.
Efficient Classification of Locally Checkable Problems in Regular Trees
(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2022) Balliu, Alkida; Brandt, Sebastian; Chang, Yi-Jun; Olivetti, Dennis; Studený, Jan; Suomela, Jukka; Department of Computer Science; Scheideler, Christian; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA); Professorship Suomela J.; Helmholtz Center for Information Security; National University of Singapore; Gran Sasso Science Institute
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)] region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in O(log n) rounds. If not, it is known that the complexity has to be Θ(n^{1/k}) for some k = 1, 2, ..., and in this case the algorithms also output the right value of the exponent k. In rooted trees in the O(log n) case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the O(log n) region remains an open question.
Exponential Speedup over Locality in MPC with Optimal Memory
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2022-10-17) Balliu, Alkida; Brandt, Sebastian; Fischer, Manuela; Latypov, Rustam; Maus, Yannic; Olivetti, Dennis; Uitto, Jara; Department of Computer Science; Scheideler, Christian; Professorship Uitto J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Gran Sasso Science Institute; Helmholtz Center for Information Security; ETH Zurich; Professorship Uitto J.; Graz University of Technology
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 independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.
Local Mending
(Springer, 2022) Balliu, Alkida; Hirvonen, Juho; Melnyk, Darya; Olivetti, Dennis; Rybicki, Joel; Suomela, Jukka; Department of Computer Science; Parter, Merav; Professorship Suomela J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA)
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.
Locally checkable labelings with small messages
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021) Balliu, Alkida; Censor-Hillel, Keren; Maus, Yannic; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Gilbert, Seth; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA); Professorship Suomela J.; Technion - Israel Institute of Technology; Universität Freiburg
A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.
Locally checkable problems in rooted trees
(Springer, 2023-09) Balliu, Alkida; Brandt, Sebastian; Chang, Yi Jun; Olivetti, Dennis; Studený, Jan; Suomela, Jukka; Tereshchenko, Aleksandr; Department of Computer Science; Computer Science Professors; Computer Science - Large-scale Computing and Data Analysis (LSCA); Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Suomela J.; Helmholtz Center for Information Security; National University of Singapore; Department of Computer Science; Gran Sasso Science Institute
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 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 Π falls in one of the following classes: it is O(1), Θ (log ∗n) , Θ (log n) , or 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 LOCAL, randomized LOCAL, deterministic CONGEST, and randomized CONGEST model. In particular, we show that randomness does not help in this setting, and the complexity class Θ (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 Π , i.e., whether Π takes O(1), Θ (log ∗n) , Θ (log n) , or nΘ (1) rounds. While the algorithm may take exponential time in the size of the description of Π , 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.
Locally Checkable Problems in Rooted Trees
(2021-07-21) Balliu, Alkida; Brandt, Sebastian; Chang, Yi-Jun; Olivetti, Dennis; Studený, Jan; Suomela, Jukka; Tereshchenko, Aleksandr; Department of Computer Science; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA); Professorship Suomela J.; ETH Zurich; Department of Computer Science; University of Freiburg
Consider any locally checkable labeling problem Π in rooted regular trees: there is a finite set of labels Σ, and for each label ∈ Σ we specify what are permitted label combinations of the children for an internal node of label (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 Π falls in one of the following classes: it is (1), Θ(log∗ ), Θ(log), or Θ(1) rounds in trees with 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 LOCAL, randomized LOCAL, deterministic CONGEST, and randomized CONGEST model. In particular, we show that randomness does not help in this setting, and the complexity class Θ(log log) 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 Π, i.e., whether Π takes (1), Θ(log∗ ), Θ(log), or Θ(1) rounds. While the algorithm may take exponential time in the size of the description of Π, 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.
New classes of distributed time complexity
(2018-06-20) Balliu, Alkida; Hirvonen, Juho; Korhonen, Janne H.; Lempiäinen, Tuomo; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.
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), Θ(n1/k), and Θ(n). It is also known that there are two gaps: one between ω(1) and o(log log∗ 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.
On Non-Cooperativeness in Social Distance Games
(Morgan Kaufmann Publishers, Inc., 2019) Balliu, Alkida; Flammini, Michele; Melideo, Giovanna; Olivetti, Dennis; Department of Computer Science; Professorship Suomela J.; University of L'Aquila
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.
Optimal Deterministic Massively Parallel Connectivity on Forests
(2023) Balliu, Alkida; Latypov, Rustam; Maus, Yannic; Olivetti, Dennis; Uitto, Jara; Department of Computer Science; Professorship Uitto J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Uitto J.; Graz University of Technology; Gran Sasso Science Institute
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.
Sinkless Orientation Made Simple
(2023-01-12) Balliu, Alkida; Korhonen, Janne H.; Kühn, Fabian; Lievonen, Henrik; Olivetti, Dennis; Pai, Shreyas; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Studený, Jan; Suomela, Jukka; Uitto, Jara; Department of Computer Science; Professorship Suomela J.; Computer Science Professors; Computer Science - Large-scale Computing and Data Analysis (LSCA); Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Uitto J.; University of Freiburg; University of Vienna; IST Austria; Aalborg University; Gran Sasso Science Institute
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.
What Can Be Verified Locally?
(2018) Balliu, Alkida; D'Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis; Department of Computer Science; Professorship Suomela J.; Gran Sasso Science Institute; CNRS
In the framework of distributed network computing, it is known that not all Turing-decidable predicates on labeled networks can be decided locally whenever the computing entities are Turing machines (TM). This holds even if nodes are running non-deterministic Turing machines (NTM). In contrast, we show that every Turing-decidable predicate on labeled networks can be decided locally if nodes are running alternating Turing machines (ATM). More specifically, we show that, for every such predicate, there is a local algorithm for ATMs, with at most two alternations, that decides whether the actual labeled network satisfies that predicate. To this aim, we define a hierarchy of classes of decision tasks, where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and the level k>1 contains those tasks solvable with ATMs with k-1 alternations. We characterize the entire hierarchy, and show that it collapses in the second level.

Browsing by Author "Balliu, Alkida"

Results Per Page

Sort Options