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

  • Principles of Algorithmic Techniques (PAT)

    • Fall 2020 -- 2024

    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
    .