26 citations · 100 across the 29 of their papers we have counts for
6 papers · 1 filter
Towards a Complexity Classification of LCL Problems in Massively Parallel Computation
Sebastian Brandt, Rustam Latypov, Jara Uitto
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 th…
Efficient CONGEST Algorithms for the Lovasz Local Lemma
Yannic Maus, Jara Uitto
We present a poly time randomized CONGEST algorithm for a natural class of Lovasz Local Lemma (LLL) instances on constant degree graphs. This implies, among other thi…
Sinkless Orientation Made Simple
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn +9
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 distribut…
Deterministic -Approximate Maximum Matching with Passes in the Semi-Streaming Model and Beyond
Manuela Fischer, Slobodan Mitrović, Jara Uitto
We present a deterministic -approximate maximum matching algorithm in passes in the semi-streaming model, solving the long-standing o…
Coloring Trees in Massively Parallel Computation
Rustam Latypov, Jara Uitto
We present time 3-coloring, maximal independent set and maximal matching algorithms for trees in the Massively Parallel Computation (MPC) model. Our algorithms a…
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs
Mélanie Cambus, Davin Choo, Havu Miikonen +1
Identifying clusters of similar elements in a set is a common task in data analysis. With the immense growth of data and physical limitations on single processor speed, it is neces…