Yannic Maus

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 2023 Conference Paper

Fast Distributed Brooks' Theorem

• Manuela Fischer
• Magnús M. Halldórsson
• Yannic Maus

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 2021 Conference Paper

Efficient randomized distributed coloring in CONGEST

• Magnús M. Halldórsson
• Fabian Kuhn
• Yannic Maus
• Tigran Tonoyan

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n -node graph G , and where the nodes of G operate in synchronous communication rounds in which they can exchange O (log n )-bit messages over all the edges of G . For graphs with maximum degree Δ, we show that the (Δ+1)-list coloring problem (and therefore also the standard (Δ+1)-coloring problem) can be solved in O (log 5 log n ) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Δ+1)-coloring algorithm in the CONGEST model had a running time of O (logΔ + log 6 log n ) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O (log n ), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.

TCS Journal 2020 Journal Article

Rumor spreading with bounded in-degree

• Sebastian Daum
• Fabian Kuhn
• Yannic Maus

In the gossip-based model of communication for disseminating information in a network, in each time unit, every node u can contact a single random neighbor v but can possibly be contacted by many nodes. In the present paper, we consider a restricted model where at each node only one incoming call can be answered in one time unit. We study the implied weaker version of the well-studied pull protocol, which we call restricted pull. We prove an exponential separation of the rumor spreading time between two variants of the protocol (the answered call among a set of calls is chosen adversarially or uniformly at random). Further, we show that if the answered call is chosen randomly, the slowdown of restricted pull versus the classic pull protocol can w. h. p. be upper bounded by O ( ψ ( G ) ⋅ log ⁡ n ), where ψ ( G ) = max { u, v } ∈ E ⁡ d ( u ) / d ( v ) ≤ Δ δ with Δ and δ being the largest and smallest degree of the network G = ( V, E ) and d ( u ) being the degree of u.

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.

STOC Conference 2017 Conference Paper

On the complexity of local distributed graph problems

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Yannic Maus

This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2 O (√log n ) . Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in log n rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and (Δ+1)-coloring) in log n rounds in the LOCAL model. Perhaps most surprisingly, we show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values. In addition, our formal framework also allows us to develop polylogarithmic-time randomized distributed algorithms in a simpler way. As a result, we provide a polylog-time distributed approximation scheme for arbitrary distributed covering and packing integer linear programs.