Title | Authors | Conference | Link |
---|---|---|---|
Adaptive Massively Parallel Coloring in Sparse Graphs | Rustam Latypov, Yannic Maus, Shreyas Pai, Jara Uitto | PODC | ArXiv |
A Single-Pass Semi-Streaming Algorithm for $(3 + \varepsilon)$-Approximate Correlation Clustering | Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, Jara Uitto | SODA | ArXiv |
Title | Authors | Conference | Link |
---|---|---|---|
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem | Mélanie Cambus, Fabian Kuhn, Shreyas Pai, Jara Uitto | DISC | ArXiv |
Conditionally Optimal Parallel Coloring of Forests | Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, Jara Uitto | DISC | ArXiv |
Distributed Symmetry Breaking on Power Graphs via Sparsification | Yannic Maus, Sakari Peltonen, Jara Uitto | PODC | Arxiv |
Fast Dynamic Programming in Trees in the MPC model | Chetan Gupta, Rustam Latypov, Yannic Maus, Shreyas Pai, Simo Särkkä, Jan Studený, Jukka Suomela, Jara Uitto, Hossein Vahidi | SPAA | ArXiv |
Adaptive Massively Parallel Connectivity in Optimal Space | Jakub Łącki, Rustam Latypov, Yannic Maus, Jara Uitto | SPAA | Arxiv |
Optimal Deterministic Massively Parallel Connectivity on Forests | Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti and Jara Uitto | SODA | ArXiv |
Sinkless Orientation Made Simple | Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, Jara Uitto | SOSA | ArXiv |
Title | Authors | Conference | Link |
---|---|---|---|
Deterministic ($1+\varepsilon$)-Approximate Maximum Matching with poly($1/\varepsilon$) Passes in the Semi-Streaming Model | Manuela Fischer, Slobodan Mitrović and Jara Uitto | STOC | ArXiv |
Exponential Speedup Over Locality in MPC with Optimal Memory | Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto | DISC | ArXiv |
Title | Authors | Conference | Link |
---|---|---|---|
Efficient CONGEST Algorithms for the Lovász Local Lemma | Yannic Maus and Jara Uitto | DISC | Arxiv |
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs | Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto | DISC | Arxiv |
Efficient Load-Balancing through Distributed Token Dropping | Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela and Jara Uitto | SPAA | Arxiv |
Title | Authors | Conference | Link |
---|---|---|---|
Tight Bounds for Deterministic High-Dimensional Grid Exploration | Sebastian Brandt, Julian Portmann and Jara Uitto | DISC | Arxiv |
Navigating an Infinite Space with Unreliable Movements | Anders Martinsson, Jara Uitto | SODA | Arxiv |
Title | Authors | Conference | Link |
---|---|---|---|
Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds | Mohsen Ghaffari, Fabian Kuhn and Jara Uitto | FOCS | Link |
Massively Parallel Computation of Matching and MIS in Sparse Graphs | Soheil Behnezhad, Sebastian Brandt, Masha Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp and Jara Uitto | PODC | Link Arxiv |
The Complexity of $(\Delta + 1)$-Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation (best student paper award) | Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto and Yufan Zheng | PODC | Arxiv |
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma | Sebastian Brandt, Yannic Maus and Jara Uitto | PODC | Arxiv |
On the Complexity of Distributed Splitting Problems | Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus and Jara Uitto | PODC | Arxiv |
Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory (best student paper award) | Sebastian Brandt, Manuela Fischer and Jara Uitto | SIROCCO | Arxiv |
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation | Mohsen Ghaffari and Jara Uitto | SODA | Arxiv |
Title | Authors | Conference | Link |
---|---|---|---|
A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration | Sebastian Brandt, Jara Uitto and Roger Wattenhofer | DISC | Link |
Distributed Recoloring | Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela and Jara Uitto | DISC | Arxiv |
Fine-grained Lower Bounds on Cops and Robbers | Sebastian Brandt, Seth Pettie and Jara Uitto | ESA | Link |
Deterministic Distributed Edge-Coloring with Fewer Colors | Mohsen Ghaffari, Fabian Kuhn, Yannic Maus and Jara Uitto | STOC | Arxiv |
The Complexity of Distributed Edge Coloring with Small Palettes | Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie and Jara Uitto | SODA | Arxiv |
Title | Authors | Conference | Link |
---|---|---|---|
Improved Distributed Degree Splitting and Edge Coloring (best paper award) | Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela and Jara Uitto | DISC | Arxiv |
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game | Sebastian Brandt, Yuval Emek, Jara Uitto and Roger Wattenhofer | ICALP | Link |
Exploring an Infinite Space with Finite Memory Scouts | Lihi Cohen, Yuval Emek, Oren Louidor and Jara Uitto | SODA | Link Arxiv |
Title | Authors | Conference | Link |
---|---|---|---|
Dynamic Networks of Finite State Machines | Yuval Emek and Jara Uitto | SIROCCO | Link |
A Lower Bound for the Distributed Lovász Local Lemma | Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela and Jara Uitto | STOC | Link Arxiv |
Overcoming Obstacles with Ants | Barbara Keller, Tobias Langner, Jara Uitto and Roger Wattenhofer | OPODIS | Link |
Title | Authors | Conference | Link |
---|---|---|---|
Randomness vs. Time in Anonymous Networks | Jara Uitto, Jochen Seidel and Roger Wattenhofer | DISC | Link |
Ignorant vs. Anonymous Recommendations | Jara Uitto and Roger Wattenhofer | ESA | Link |
Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond | Klaus-Tycho Förster, Rijad Nuridini, Jara Uitto and Roger Wattenhofer | SIROCCO | Link |
Title | Authors | Conference | Link |
---|---|---|---|
SpareEye: A Smart Phone App that Enhances the Safety of the Inattentionally Blind | Klaus-Tycho Förster, Alex Gross, Nino Hail, Jara Uitto and Roger Wattenhofer | MUM | Link |
Fault-Tolerant ANTS | Tobias Langner, David Stolz, Jara Uitto and Roger Wattenhofer | DISC | Link |
How Many Ants Does It Take to Find the Food? | Yuval Emek, Tobias Langner, David Stolz, Jara Uitto and Roger Wattenhofer | SIROCCO | Link |
Solving the ANTS Problem with Asynchronous Finite State Machines | Yuval Emek, Tobias Langner, Jara Uitto and Roger Wattenhofer | ICALP | Link |
Title | Authors | Conference | Link |
---|---|---|---|
On Competitive Recommendations | Jara Uitto and Roger Wattenhofer | ALT | Link |
Title | Authors | Conference | Link |
---|---|---|---|
A Local 2-Approximation Algorithm for the Vertex Cover Problem | Matti Astrand, Patrik Floreen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela and Jara Uitto | DISC | Link |
Title | Authors | Journal | Year | Link |
---|---|---|---|---|
Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory | Sebastian Brandt, Manuela Fischer and Jara Uitto | Theorerical Computer Science | 2021 | Link |
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game | Sebastian Brandt, Jara Uitto and Roger Wattenhofer | Theoretical Computer Science | 2020 | Link |
A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration | Sebastian Brandt, Jara Uitto and Roger Wattenhofer | Distributed Computing | 2020 | Link |
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma | Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie and Jara Uitto | Transactions on Algorithms | 2019 | Link |
Improved Distributed Degree Splitting and Edge Coloring | Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela and Jara Uitto | Distributed Computing | 2019 | Link |
Dynamic Networks of Finite State Machines | Yuval Emek and Jara Uitto | Theoretical Computer Science | 2017 | Link |
On Competitive Recommendations | Jara Uitto and Roger Wattenhofer | Theoretical Computer Science | 2016 | Link |
How Many Ants Does it Take to Find the Food? | Yuval Emek, Tobias Langner, David Stolz Jara Uitto and Roger Wattenhofer | Theoretical Computer Science | 2015 | Link |