Sublinear Algorithms Group

Team Members

  • Jara Uitto
  • Mélanie Cambus ( PhD student 11.2020 → )
  • Havu Miikonen ( Master's student / research assistant)
    6.2020 →
  • Rustam Latypov ( Master's student / research assistant)
    5.2020 →
  • Sander Aarts ( Civil Service 8.2020 → )

Alumni

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
img

Master's thesis

Interested in doing your master's thesis in my group? Drop me an email and we can discuss ideas for topics.

Teaching

Fall 2020

Professional Activities

Upcoming/Current

Past

  • PC: DISC 2019, SIROCCO 2020, OPODIS 2020
  • Program Chair: ADGA 2020
  • Publications


    Recent Work

    TitleAuthorsLink
    Massively Parallel Correlation Clustering in Bounded Arboricity Graphs Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto Manuscript Arxiv
    Efficient Load-Balancing through Distributed Token Dropping Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela and Jara Uitto Manuscript Arxiv

    Conference Papers

    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
    The Complexity of (Δ + 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

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