Sebastian Brandt

Dennis Olivetti

SIAM J. Comput., 2022

Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees.

[BibT_eX]

[DOI]

CoRR, 2022

Efficient Classification of Local Problems in Regular Trees.

[BibT_eX]

[DOI]

CoRR, 2022

Exponential Speedup over Locality in MPC with Optimal Memory.

[BibT_eX]

[DOI]

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

Efficient Classification of Locally Checkable Problems in Regular Trees.

[BibT_eX]

[DOI]

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

Distributed ∆-coloring plays hide-and-seek.

[BibT_eX]

[DOI]

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

The Landscape of Distributed Complexities on Trees and Beyond.

[BibT_eX]

[DOI]

Christoph Grunau

Václav Rozhon

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Distributed Edge Coloring in Time Polylogarithmic in Δ.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

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

[BibT_eX]

[DOI]

Manuela Fischer

Theor. Comput. Sci., 2021

Lower Bounds for Maximal Matchings and Maximal Independent Sets.

[BibT_eX]

[DOI]

J. ACM, 2021

Almost global problems in the LOCAL model.

[BibT_eX]

[DOI]

Distributed Comput., 2021

Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees.

[BibT_eX]

[DOI]

Rustam Latypov

CoRR, 2021

On Homomorphism Graphs.

[BibT_eX]

[DOI]

CoRR, 2021

Distributed Δ-Coloring Plays Hide-and-Seek.

[BibT_eX]

[DOI]

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

Locally Checkable Problems in Rooted Trees.

[BibT_eX]

[DOI]

Aleksandr Tereshchenko

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

The Randomized Local Computation Complexity of the Lovász Local Lemma.

[BibT_eX]

[DOI]

Christoph Grunau

Václav Rozhon

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

Wireless evacuation on <i>m</i> rays with <i>k</i> searchers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Distributed Comput., 2020

Classification of Distributed Binary Labeling Problems.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 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

How much does randomness help with locally checkable problems?

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Brief Announcement: Classification of Distributed Binary Labeling Problems.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants.

[BibT_eX]

[DOI]

Dennis Olivetti

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

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

[BibT_eX]

[DOI]

Christoph Grunau

Václav Rozhon

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

2019

SIROCCO 2019 Review.

[BibT_eX]

[DOI]

Manuela Fischer

SIGACT News, 2019

Approximating Small Balanced Vertex Separators in Almost Linear Time.

[BibT_eX]

[DOI]

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

An Automatic Speedup Theorem for Distributed Problems.

[BibT_eX]

[DOI]

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

The Distributed Complexity of Locally Checkable Problems on Paths is Decidable.

[BibT_eX]

[DOI]

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

2018

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

[BibT_eX]

[DOI]

Manuela Fischer

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

Augmenting flows for the consistent migration of multi-commodity single-destination flows in SDNs.

[BibT_eX]

[DOI]

Klaus-Tycho Foerster

Pervasive Mob. Comput., 2017

Tight Bounds for Asynchronous Collaborative Grid Exploration.

[BibT_eX]

[DOI]

CoRR, 2017

Wireless Evacuation on m Rays with k Searchers.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2017

LCL Problems on Grids.

[BibT_eX]

[DOI]

Patric R. J. Östergård

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

Collaboration Without Communication: Evacuating Two Robots from a Disk.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

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

On consistent migration of flows in SDNs.

[BibT_eX]

[DOI]

Klaus-Tycho Förster

Proceedings of the 35th Annual IEEE International Conference on Computer Communications, 2016

Augmenting anycast network flows.

[BibT_eX]

[DOI]

Klaus-Tycho Förster