Jara Uitto

SODA Conference 2025 Conference Paper

On the Locality of Hall's Theorem

• Sebastian Brandt 0002
• Yannic Maus
• Ananth Narayanan
• Florian Schager
• Jara Uitto

SODA Conference 2024 Conference Paper

A (3 + ɛ)-Approximate Correlation Clustering Algorithm in Dynamic Streams

• Mélanie Cambus
• Fabian Kuhn
• Etna Lindy
• Shreyas Pai
• Jara Uitto

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming and parallel algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimilar. The task is to partition the elements and the objective is to minimize disagreements, that is, the number of dissimilar elements grouped together and similar elements that get separated. Our main contribution is a semi-streaming algorithm that achieves a (3 + ɛ)-approximation to the minimum number of disagreements using a single pass over the stream. In addition, the algorithm also works for dynamic streams. Our approach builds on the analysis of the PIVOT algorithm by Ailon, Charikar, and Newman [JACM’08] that obtains a 3-approximation in the centralized setting. Our design allows us to sparsify the input graph by ignoring a large portion of the nodes and edges without a large extra cost as compared to the analysis of PIVOT. This sparsification makes our technique applicable in several models of massive graph processing, such as semi-streaming and Massively Parallel Computing (MPC), where sparse graphs can typically be handled much more efficiently. Our work improves on the approximation ratio of the recent single-pass 5-approximation algorithm and on the number of passes of the recent O (1/ɛ)-pass (3 + ɛ)-approximation algorithm [Behnezhad, Charikar, Ma, Tan FOCS’22, SODA’23]. Our algorithm is also more robust and can be applied in dynamic streams. Furthermore, it is the first single pass (3 + ɛ)-approximation algorithm that uses polynomial post-processing time.

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

Deterministic (1+ ε )-approximate maximum matching with poly(1/ ε ) passes in the semi-streaming model and beyond

• Manuela Fischer
• Slobodan Mitrovic
• Jara Uitto

We present a deterministic (1+ε)-approximate maximum matching algorithm in poly (1/ε) passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on 1/ε. Our algorithm exponentially improves on the well-known randomized (1/ε) O (1/ε) -pass algorithm from the seminal work by McGregor [APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity [FSTTCS18]. Up to polynomial factors in 1/ε, our work matches the state-of-the-art deterministic (log n / loglog n ) · (1/ε)-pass algorithm by Ahn and Guha [TOPC18], that is allowed a dependence on the number of nodes n . Our result also makes progress on the Open Problem 60 at sublinear.info. Moreover, we design a general framework that simulates our approach for the streaming setting in other models of computation. This framework requires access to an algorithm computing a maximal matching and an algorithm for processing disjoint ( 1 / ε)-size connected components. Instantiating our framework in CONGEST yields a (log n , 1/ε) round algorithm for computing (1+ε)-approximate maximum matching. In terms of the dependence on 1/ε, this result improves exponentially state-of-the-art result by Lotker, Patt-Shamir, and Pettie [LPSP15]. Our framework leads to the same quality of improvement in the context of the Massively Parallel Computation model as well.

TCS Journal 2021 Journal Article

Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory

• Sebastian Brandt
• Manuela Fischer
• Jara Uitto

Recently, studying fundamental graph problems in the Massively Parallel Computation ( MPC ) framework, inspired by the MapReduce paradigm, has gained a lot of attention. An assumption common to a vast majority of approaches is to allow Ω ˜ ( n ) memory per machine, where n is the number of nodes in the graph and Ω ˜ hides polylogarithmic factors. However, as pointed out by Karloff et al. [SODA'10] and Czumaj et al. [STOC'18], it might be unrealistic for a single machine to have linear or only slightly sublinear memory. In this paper, we thus study a more practical variant of the MPC model which only requires substantially sublinear or even subpolynomial memory per machine. In contrast to the linear-memory MPC model and also to streaming algorithms, in this low-memory MPC setting, a single machine will only see a small number of nodes in the graph. We introduce a new and strikingly simple technique to cope with this imposed locality. In particular, we show that the Maximal Independent Set ( MIS ) problem can be solved efficiently, that is, in O ( log 3 ⁡ log ⁡ n ) rounds, when the input graph is a tree. This constitutes an almost exponential speed-up over the low-memory MPC algorithm in O ˜ ( log ⁡ n ) rounds in a concurrent work by Ghaffari and Uitto [SODA'19] and substantially reduces the local memory from Ω ˜ ( n ) required by the recent O ( log ⁡ log ⁡ n ) -round MIS algorithm of Ghaffari et al. [PODC'18] to n ε for any ε > 0, without incurring a significant loss in the round complexity. Moreover, it demonstrates how to make use of the all-to-all communication in the MPC model to almost exponentially improve on the corresponding bound in the LOCAL and PRAM models by Lenzen and Wattenhofer [PODC'11].

TCS Journal 2020 Journal Article

A tight lower bound for the capture time of the Cops and Robbers game

• Sebastian Brandt
• Yuval Emek
• Jara Uitto
• Roger Wattenhofer

For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O ( n ) time, and that there exist graphs in which this capture time is tight. When k ≥ 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O ( n k + 1 ), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O ( n k + 1 ) bound is asymptotically tight for any constant k ≥ 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

TCS Journal 2020 Journal Article

Dynamic networks of finite state machines

• Yuval Emek
• Jara Uitto

Like distributed systems, biological multicellular processes are subject to dynamic changes and a biological system will not pass the survival-of-the-fittest test unless it exhibits certain features that enable fast recovery from these changes. In most cases, the types of dynamic changes a biological process may experience and its desired recovery features differ from those traditionally studied in the distributed computing literature. In particular, a question seldomly asked in the context of distributed digital systems, and that is crucial in the context of biological cellular networks, is whether the system can keep the changing components confined so that only nodes in their vicinity may be affected by the changes, but nodes sufficiently far away from any changing component remain unaffected. Based on this notion of confinement, we propose a new metric for measuring the dynamic changes recovery performance in distributed network algorithms operating under the Stone Age model (Emek and Wattenhofer, 2013) [1], where the class of dynamic topology changes we consider includes inserting/deleting an edge, deleting a node together with its incident edges, and inserting a new isolated node. Our main technical contribution is a distributed algorithm for maximal independent set (MIS) in synchronous networks subject to these topology changes that performs well in terms of the aforementioned new metric. Specifically, our algorithm guarantees that nodes which do not experience a topology change in their immediate vicinity are not affected and that all surviving nodes (including the affected ones) perform O ( ( C + 1 ) log 2 ⁡ n ) computationally-meaningful steps, where C is the number of topology changes; in other words, each surviving node performs O ( log 2 ⁡ n ) steps when amortized over the number of topology changes. This is accompanied by a simple example demonstrating that the linear dependency on C cannot be avoided.

SODA Conference 2020 Conference Paper

Navigating an Infinite Space with Unreliable Movements

• Anders Martinsson
• Jara Uitto

FOCS Conference 2019 Conference Paper

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Jara Uitto

We present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC 1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.

SODA Conference 2019 Conference Paper

Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation

• Mohsen Ghaffari 0001
• Jara Uitto

We introduce a method for “sparsifying” distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA). MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic O (log n )-round parallel (PRAM) counterparts for problems such as Maximal Independent Set (MIS), Maximal Matching, 2-Approximation of Minimum Vertex Cover, and (1 + ∊)-Approximation of Maximum Matching. Currently, all such MPC algorithms require memory of per machine: Czumaj et al. [STOC'18] were the first to handle memory, running in O ((log log n ) 2 ) rounds, who improved on the n 1+Ω(1) memory requirement of the O (1)-round algorithm of Lattanzi et al [SPAA'11]. We obtain -round MPC algorithms for all these four problems that work even when each machine has strongly sublinear memory, e. g. , n α for any constant α ∊ (0, 1). Here, Δ denotes the maximum degree. These are the first sublogarithmictime MPC algorithms for (the general case of) these problems that break the linear memory barrier. LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity Δ O (log Δ) poly(log n ), by Ghaffari [SODA'16], which improved over the Δ O (log 2 Δ) poly(log n ) bound of Levi et al. [Algorithmica'17]. As pointed out by Rubinfeld, obtaining a query complexity of poly(Δ log n ) remains a central open question. Ghaffari's bound almost reaches a barrier common to all known MIS LCAs, which sim-ulate a distributed algorithm by learning the full local topology, à la Parnas-Ron [TCS'07]. There is a barrier because the distributed complexity of MIS has a lower bound of, by results of Kuhn, et al. [JACM'16], which means this methodology cannot go below query complexity. We break this barrier and obtain an LCA for MIS that has a query complexity Δ O (log log Δ) poly(log n ).

STOC Conference 2018 Conference Paper

Deterministic distributed edge-coloring with fewer colors

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Yannic Maus
• Jara Uitto

We present a deterministic distributed algorithm, in the LOCAL model, that computes a (1+ o (1))Δ-edge-coloring in polylogarithmic-time, so long as the maximum degree Δ=Ω(log n ). For smaller Δ, we give a polylogarithmic-time 3Δ/2-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of 2Δ−1 colors, and they improve significantly on the recent polylogarithmic-time (2Δ−1)(1+ o (1))-edge-coloring of Ghaffari and Su [SODA’17] and the (2Δ−1)-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS’17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.

SODA Conference 2018 Conference Paper

The Complexity of Distributed Edge Coloring with Small Palettes

• Yi-Jun Chang
• Qizheng He
• Wenzheng Li
• Seth Pettie
• Jara Uitto

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. • We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(log Δ log n ) time w. h. p. and Ω(log Δ n ) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones. • We give a randomized edge coloring algorithm that can use palette sizes as small as, which is a natural barrier for randomized approaches. The running time of the algorithm is at most O (log Δ · T LLL ), where T LLL is the complexity of a permissive version of the constructive Lovász local lemma. • We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ∊ )Δ-edge coloring algorithm for trees running in O (log log n ) time. This algorithm arises from two new results: a deterministic O (log n )-time LLL algorithm for tree-structured instances, and a randomized O (log log n )-time graph shattering method for breaking the dependency graph into independent O (log n )-size LLL instances. • A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e. g. , via “augmenting paths. ” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n ). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence of O (log Δ n )-length augmenting paths.

SODA Conference 2017 Conference Paper

Exploring an Infinite Space with Finite Memory Scouts

• Lihi Cohen
• Yuval Emek
• Oren Louidor
• Jara Uitto

Consider a small number of scouts exploring the infinite d- dimensional grid with the aim of hitting a hidden target point. Each scout is controlled by a probabilistic finite automaton that determines its movement (to a neighboring grid point) based on its current state. The scouts, that operate under a fully synchronous schedule, communicate with each other (in a way that affects their respective states) when they share the same grid point and operate independently otherwise. Our main research question is: How many scouts are required to guarantee that the target admits a finite mean hitting time? Recently, it was shown that d + 1 is an upper bound on the answer to this question for any dimension d ≥ 1 and the main contribution of this paper comes in the form of proving that this bound is tight for d ∊ {1, 2}.

STOC Conference 2016 Conference Paper

A lower bound for the distributed Lovász local lemma

• Sebastian Brandt 0002
• Orr Fischer
• Juho Hirvonen
• Barbara Keller
• Tuomo Lempiäinen
• Joel Rybicki
• Jukka Suomela
• Jara Uitto

We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Omega(log log n) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d = O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of O(log n) rounds in bounded-degree graphs, and the best lower bound before our work was Omega(log* n) rounds [Chung et al. 2014].

TCS Journal 2016 Journal Article

On competitive recommendations

• Jara Uitto
• Roger Wattenhofer

We are given an unknown binary matrix, where the entries correspond to preferences of users on items. We want to find at least one 1-entry in each row with a minimum number of queries. The number of queries needed heavily depends on the input matrix and a straightforward competitive analysis yields bad results for any online algorithm. Therefore, we analyze our algorithm against a weaker offline algorithm that is given the number of users and a probability distribution according to which the preferences of the users are chosen. We show that our algorithm has an O ( n log 2 ⁡ n ) overhead in comparison to the weaker offline solution. Furthermore, we show that the corresponding overhead for any online algorithm is Ω ( n ), which shows that the performance of our algorithm is within an O ( log 2 ⁡ n ) multiplicative factor from optimal in this sense.

TCS Journal 2015 Journal Article

How many ants does it take to find the food?

• Yuval Emek
• Tobias Langner
• David Stolz
• Jara Uitto
• Roger Wattenhofer

Consider the Ants Nearby Treasure Search (ANTS) problem, where n mobile agents, initially placed at the origin of an infinite grid, collaboratively search for an adversarially hidden treasure. The agents are controlled by deterministic/randomized finite or pushdown automata and are able to communicate with each other through constant-size messages. We show that the minimum number of agents required to solve the ANTS problem crucially depends on the computational capabilities of the agents as well as the timing parameters of the execution environment. We give lower and upper bounds for different scenarios.