Jara Uitto

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

2022

Exponential Speedup over Locality in MPC with Optimal Memory.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond.

[BibT_eX]

[DOI]

Slobodan Mitrovic

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees.

[BibT_eX]

[DOI]

Rustam Latypov

CoRR, 2021

Deterministic (1+ε)-Approximate Maximum Matching with poly(1/ε) Passes in the Semi-Streaming Model.

[BibT_eX]

[DOI]

Slobodan Mitrovic

CoRR, 2021

Deterministic 3-Coloring of Trees in the Sublinear MPC model.

[BibT_eX]

[DOI]

Rustam Latypov

CoRR, 2021

Efficient CONGEST Algorithms for the Lovász Local Lemma.

[BibT_eX]

[DOI]

Yannic Maus

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Massively Parallel Correlation Clustering in Bounded Arboricity Graphs.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees.

[BibT_eX]

[DOI]

Rustam Latypov

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Efficient Load-Balancing through Distributed Token Dropping.

[BibT_eX]

[DOI]

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

2020

Dynamic networks of finite state machines.

[BibT_eX]

[DOI]

Yuval Emek

Theor. Comput. Sci., 2020

A tight lower bound for the capture time of the Cops and Robbers game.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Improved distributed degree splitting and edge coloring.

[BibT_eX]

[DOI]

Distributed Comput., 2020

A tight lower bound for semi-synchronous collaborative grid exploration.

[BibT_eX]

[DOI]

Distributed Comput., 2020

Tight Bounds for Deterministic High-Dimensional Grid Exploration.

[BibT_eX]

[DOI]

Julian Portmann

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Navigating an Infinite Space with Unreliable Movements.

[BibT_eX]

[DOI]

Anders Martinsson

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

SIROCCO 2019 Review.

[BibT_eX]

[DOI]

SIGACT News, 2019

Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma.

[BibT_eX]

[DOI]

Yannic Maus

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Massively Parallel Computation of Matching and MIS in Sparse Graphs.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Richard M. Karp

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

On the Complexity of Distributed Splitting Problems.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Fabian Kuhn

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation.

[BibT_eX]

[DOI]

Mohsen Ghaffari

CoRR, 2018

Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model.

[BibT_eX]

[DOI]

CoRR, 2018

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with nε Memory per Machine.

[BibT_eX]

[DOI]

CoRR, 2018

Distributed Recoloring.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Deterministic distributed edge-coloring with fewer colors.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Complexity of Distributed Edge Coloring with Small Palettes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fine-grained Lower Bounds on Cops and Robbers.

[BibT_eX]

[DOI]

Seth Pettie

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Tight Bounds for Asynchronous Collaborative Grid Exploration.

[BibT_eX]

[DOI]

CoRR, 2017

Exploring an Infinite Space with Finite Memory Scouts.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

On competitive recommendations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

A lower bound for the distributed Lovász local lemma.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Collaboration in Multi-Agent Systems: Adaptivity and Active Learning.

[BibT_eX]

[DOI]

PhD thesis, 2015

How many ants does it take to find the food?

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Randomness vs. Time in Anonymous Networks.

[BibT_eX]

[DOI]

Jochen Seidel

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2015

Overcoming Obstacles with Ants.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Principles of Distributed Systems, 2015

Ignorant vs. Anonymous Recommendations.

[BibT_eX]

[DOI]