Jara Uitto
YOU?
Author Swipe
View article: Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs
Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs Open
Given a graph G = (V, E), a β-ruling set is a subset S ⊆ V that is i) independent, and ii) every node υ ∈ V has a node of S within distance β. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees …
View article: A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams Open
Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimil…
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: On the Locality of Hall's Theorem
On the Locality of Hall's Theorem Open
The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponen…
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: Adaptive Massively Parallel Coloring in Sparse Graphs
Adaptive Massively Parallel Coloring in Sparse Graphs Open
Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model that captures the central challenges in data center computa…
View article: Distributed Symmetry Breaking on Power Graphs via Sparsification
Distributed Symmetry Breaking on Power Graphs via Sparsification Open
Funding Information: Saku Peltonen is supported by the Academy of Finland, Grant 334238. Publisher Copyright: © 2023 Owner/Author(s).
View article: Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem Open
In this work, we present a constant-round algorithm for the $2$-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal tota…
View article: Fast Dynamic Programming in Trees in the MPC Model
Fast Dynamic Programming in Trees in the MPC Model Open
Funding Information: We are grateful to Alkida Balliu, Darya Melnyk, and Dennis Olivetti for several fruitful discussions, and to the anonymous reviewers for their helpful feedback on prior versions of this work. This work was supported in…
View article: Adaptive Massively Parallel Connectivity in Optimal Space
Adaptive Massively Parallel Connectivity in Optimal Space Open
Funding Information: Supported by the Academy of Finland, Grant 334238 Publisher Copyright: © 2023 Owner/Author.
View article: Fast Dynamic Programming in Trees in the MPC Model
Fast Dynamic Programming in Trees in the MPC Model Open
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in $O(\log D)$ rounds in the massively parallel computation model (MPC), with $O(n^δ)$ words of local memory per machine, for any given …
View article: Distributed Symmetry Breaking on Power Graphs via Sparsification
Distributed Symmetry Breaking on Power Graphs via Sparsification Open
In this paper, we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, whe…
View article: Adaptive Massively Parallel Connectivity in Optimal Space
Adaptive Massively Parallel Connectivity in Optimal Space Open
We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in $O(\log…
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: Conditionally Optimal Parallel Coloring of Forests
Conditionally Optimal Parallel Coloring of Forests Open
We show the first conditionally optimal deterministic algorithm for 3-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in O(log log n) rounds and uses optimal global space. The best previous …
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: 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: Deterministic (1+ <i>𝜀</i> )-approximate maximum matching with poly(1/ <i>𝜀</i> ) passes in the semi-streaming model and beyond
Deterministic (1+ <i>𝜀</i> )-approximate maximum matching with poly(1/ <i>𝜀</i> ) passes in the semi-streaming model and beyond Open
Funding Information: The second author of this work was supported by the Swiss NSF Grant under Grant No. P400P2_191122/1. Most of this work was done while the author was affiliated with MIT. The third author was supported in part by the Ac…
View article: A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams Open
Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimil…
View article: Towards a Complexity Classification of LCL Problems in Massively Parallel Computation
Towards a Complexity Classification of LCL Problems in Massively Parallel Computation Open
In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method that solves most locally checkable labeling (LCL) problems ex…
View article: Sinkless Orientation Made Simple
Sinkless Orientation Made Simple Open
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 sink…
View article: Efficient CONGEST Algorithms for the Lovasz Local Lemma
Efficient CONGEST Algorithms for the Lovasz Local Lemma Open
We present a poly $\log \log n$ time randomized CONGEST algorithm for a natural class of Lovasz Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complex…
View article: Efficient Load-Balancing through Distributed Token Dropping
Efficient Load-Balancing through Distributed Token Dropping Open
We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and …
View article: Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model
Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model Open
We present a deterministic $(1+\varepsilon)$-approximate maximum matching algorithm in $\mathsf{poly}(1/\varepsilon)$ passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dep…
View article: Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond Open
We present a deterministic $(1+\varepsilon)$-approximate maximum matching algorithm in $\mathsf{poly} 1/\varepsilon$ passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the depe…
View article: Coloring Trees in Massively Parallel Computation
Coloring Trees in Massively Parallel Computation Open
We present $O(\log^2 \log n)$ time 3-coloring, maximal independent set and maximal matching algorithms for trees in the Massively Parallel Computation (MPC) model. Our algorithms are deterministic, apply to arbitrary-degree trees and work …