Jara Uitto

I am an assistant professor in the Computer Science department at Aalto University.

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

Research Group

Alumni

Teaching

Fall 2020

Recent Work

TitleAuthorsLink
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
Improved Distributed Degree Splitting and Edge Coloring Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela and Jara Uitto Distributed Computing 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