Yannic Maus
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yannic Maus has a total of 37 co-authors. Here are the top co-authors by number of shared publications:
- Jara Uitto
Aalto University, Espoo, Finland
7 shared publications - Jara Uitto
Aalto University, Helsinki, Finland
5 shared publications - Rustam Latypov
Department of Computer Science, Aalto University, Espoo, Finland
5 shared publications - Shreyas Pai
IIT Madras, Chennai, India
4 shared publications - Magnus Mar Halldorsson
Reykjavik University, Reykjavik, Iceland
3 shared publications - Manuel Jakob
TU Graz, Graz, Austria
3 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 366-379
Deterministic Distance Approximation in MPC via Improved Hitting Sets
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 366-379
Open AccessDeterministic Distance Approximation in MPC via Improved Hitting Sets
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 40-43
Brief Announcement: Deterministic Edge Coloring with few Colors in CONGEST
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 40-43
Open AccessBrief Announcement: Deterministic Edge Coloring with few Colors in CONGEST
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 329-332
Brief Announcement: Fast Deterministic Distributed Degree Splitting
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 329-332
Open AccessBrief Announcement: Fast Deterministic Distributed Degree Splitting
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1937-1948
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1937-1948
Open AccessSublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
- 24 May 2026
- Published by Springer Nature
- p. 391-410
Towards Optimal Distributed Delta Coloring
- 24 May 2026
- Published by Springer Nature
- p. 234-252
Distributed Sparsest Cut via Eigenvalue Estimation
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 88-98
Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 88-98
Open AccessNearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 318-321
Brief Announcement: Towards Optimal Distributed Delta Coloring
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 318-321
Open AccessBrief Announcement: Towards Optimal Distributed Delta Coloring
- Open Access
- 25 May 2025
- Published by Springer Nature in Distributed Computing
- Vol. 38 (3) , 261-296
Distributed symmetry breaking on power graphs via sparsification
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, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph $$G^k$$ , where each node of the communication network G is connected to all of its k-hop neighbors. A $$\beta $$ -ruling set is a set of non-adjacent nodes such that each node in G has a ruling neighbor within $$\beta $$ hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM’16, Ghaffari SODA’19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of $$G^k$$ in essentially the same time as they can be computed in G. Our main contribution is a deterministic $${{\,\textrm{poly}\,}}(k,\log n)$$ time algorithm for computing k-ruling sets of $$G^k$$ , which (for k > 1) improves exponentially on the current state-of-the-art runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. We also revisit the shattering algorithm for MIS [BEPS JACM’16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA’16].- 25 May 2025
- Published by Springer Nature in Distributed Computing
- Vol. 38 (3) , 261-296
Open AccessDistributed symmetry breaking on power graphs via sparsification
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, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph $$G^k$$ , where each node of the communication network G is connected to all of its k-hop neighbors. A $$\beta $$ -ruling set is a set of non-adjacent nodes such that each node in G has a ruling neighbor within $$\beta $$ hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM’16, Ghaffari SODA’19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of $$G^k$$ in essentially the same time as they can be computed in G. Our main contribution is a deterministic $${{\,\textrm{poly}\,}}(k,\log n)$$ time algorithm for computing k-ruling sets of $$G^k$$ , which (for k > 1) improves exponentially on the current state-of-the-art runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. We also revisit the shattering algorithm for MIS [BEPS JACM’16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA’16]. - Open Access
- 26 February 2025
- Published by Springer Nature in Distributed Computing
- Vol. 38 (4) , 397-434
Exponential speedup over locality in MPC with optimal memory
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 independent set, and colorings. A successful line of research has been studying the complexities of s on paths/cycles, trees, and general graphs, providing many interesting results for the model of distributed computing. In this work, we initiate the study of problems in the low-space Massively Parallel Computation () model. In particular, on forests, we provide a method that, given the complexity of an problem in the model, automatically provides an exponentially faster algorithm for the low-space setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the setting are obtained through lower bounds for problems in the distributed setting in tree-like networks (either trees or high-girth graphs), and hence the problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., 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, hence using optimal memory requires new solutions.
- 26 February 2025
- Published by Springer Nature in Distributed Computing
- Vol. 38 (4) , 397-434
Open AccessExponential speedup over locality in MPC with optimal memory
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 independent set, and colorings. A successful line of research has been studying the complexities of s on paths/cycles, trees, and general graphs, providing many interesting results for the model of distributed computing. In this work, we initiate the study of problems in the low-space Massively Parallel Computation () model. In particular, on forests, we provide a method that, given the complexity of an problem in the model, automatically provides an exponentially faster algorithm for the low-space setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the setting are obtained through lower bounds for problems in the distributed setting in tree-like networks (either trees or high-girth graphs), and hence the problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., 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, hence using optimal memory requires new solutions.