Sublinear Algorithms Group

Aalto University
Computer Science department

Team Members

Alumni

  • Shreyas Pai, Postdoc, August 2021 → March 2024. Now an assistant professor at IIT Madras
  • Ronja Stimpert, research and teaching assistant, May 2023 → December 2023
  • Chetan Gupta, Postdoc, March 2023 → October 2023
  • Santeri Koivula, research assistant, June 2023 → August 2023
  • Saku Peltonen, research assistant/Master's student,
    March 2022 → June 2023
  • Etna Lindy, research assistant,
    June 2022 → May 2024
  • Joona Särkijärvi, research assistant,
    May 2022 → September 2022
  • Navid EslamiAmirabadi, research assistant,
    July 2022 → September 2022
  • Havu Miikonen, Master's student / research assistant,
    2020 → 2021
  • Sander Aarts, Civil Service, August 2020 → July 2021
img

Jara Uitto

I am an assistant professor in the Aalto CS theory group. Since 2020, my research is supported by the Academy of Finland.

Research Interests

My research is mainly on theoretical computer science. Most of my work is on distributed computing, including local and massively parallel graph algorithms. I am also interested in collaborative graph searching.

I like all sorts of puzzles that are easy to state and not (necessarily) so easy to solve. I am always up for new topics and ideas.

Besides research, I enjoy climbing/bouldering. In case you meet me somewhere and also enjoy sports, I would be delighted to join forces.

Contact Information

Email:
Office: B309, Computer Science Building
Konemiehentie 2, 02150 Espoo, Finland
Google Scholar
Orcid: 0000-0002-5179-5056
img

Master's thesis

Interested in doing your master's thesis in my group? You can find the list of available topics in the CS wiki, including the running topics from our group. In case those topics are not stimulating, drop me an email and we can discuss more ideas.

Teaching

Fall 2024

Fall 2020, 2021, 2022, 2023

Fall 2022, 2023

Professional Activities

Upcoming/Current

Past

Publications


Conference Papers

2025

TitleAuthorsConferenceLink
On the Locality of Hall's Theorem Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, Jara Uitto SODA

2024

TitleAuthorsConferenceLink
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

2023

TitleAuthorsConferenceLink
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

2022

TitleAuthorsConferenceLink
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

2021

TitleAuthorsConferenceLink
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

2020

TitleAuthorsConferenceLink
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

2019

TitleAuthorsConferenceLink
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

2018

TitleAuthorsConferenceLink
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

2017

TitleAuthorsConferenceLink
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

2016

TitleAuthorsConferenceLink
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

2015

TitleAuthorsConferenceLink
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

2014

TitleAuthorsConferenceLink
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

2013

TitleAuthorsConferenceLink
On Competitive Recommendations Jara Uitto and Roger Wattenhofer ALT Link

2009

TitleAuthorsConferenceLink
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

Journals Papers

TitleAuthorsJournalYearLink
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
.