Sebastian Brandt

I am a postdoc in the Discrete and Distributed Algorithms Group at ETH Zurich, led by Prof. Ghaffari. I received my PhD from ETH in the beginning of 2018, under the supervision of Prof. Wattenhofer.
My research mostly revolves around questions in algorithm design and analysis. One of my main goals is to understand the nature of locality in algorithms: What can be computed with access to only a small, local part of the input data? What are the fundamental limitations due to locality, and how can we prove them? Naturally, my research focuses on distributed and parallel algorithms, but I am also interested in understanding how locality affects computation in general, and extending local techniques to a broader range of areas in computer science. Other more-or-less related topics I am curious about include biologically-inspired algorithms, mobile agents, or massively parallel computation.



Manuscripts

Locally Checkable Problems in Rooted Trees
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko
[arXiv]

Efficient Load-Balancing through Distributed Token Dropping
Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto
[arXiv]



Conference Publications

Distributed Lower Bounds for Ruling Sets
Alkida Balliu, Sebastian Brandt, and Dennis Olivetti
IEEE Symposium on Foundations of Computer Science (FOCS) 2020.
[arXiv]

Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
Sebastian Brandt and Dennis Olivetti
ACM Symposium on Principles of Distributed Computing (PODC) 2020.
[arXiv]

How Much Does Randomness Help with Locally Checkable Problems?
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela
ACM Symposium on Principles of Distributed Computing (PODC) 2020.
[arXiv]

Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Christoph Grunau, and Václav Rozhoň
ACM Symposium on Principles of Distributed Computing (PODC) 2020.
[arXiv]

Tight Bounds for Deterministic High-Dimensional Grid Exploration
Sebastian Brandt, Julian Portmann, Jara Uitto
International Symposium on Distributed Computing (DISC) 2020.
[arXiv]

Classification of Distributed Binary Labeling Problems
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela
International Symposium on Distributed Computing (DISC) 2020.
[arXiv]

Lower Bounds for Maximal Matchings and Maximal Independent Sets
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela
IEEE Symposium on Foundations of Computer Science (FOCS) 2019.
Best Paper Award at FOCS'19
[arXiv]

An Automatic Speedup Theorem for Distributed Problems
Sebastian Brandt
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
[arXiv]

A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Yannic Maus, and Jara Uitto
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
[arXiv]

The Distributed Complexity of Locally Checkable Problems on Paths Is Decidable
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
[arXiv]

Massively Parallel Computation of Matching and MIS in Sparse Graphs
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
A merge of [arXiv] and [arXiv]

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
Sebastian Brandt, Manuela Fischer, and Jara Uitto
International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2019.
Best Student Paper Award at SIROCCO'19
[arXiv]

Almost Global Problems in the LOCAL Model
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela
International Symposium on Distributed Computing (DISC) 2018.
[arXiv]

A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration
Sebastian Brandt, Jara Uitto, and Roger Wattenhofer
International Symposium on Distributed Computing (DISC) 2018.
[DOI]

Fine-grained Lower Bounds on Cops and Robbers
Sebastian Brandt, Seth Pettie, and Jara Uitto
European Symposium on Algorithms (ESA) 2018.
[DOI]

LCL Problems on Grids
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergard, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański
ACM Symposium on Principles of Distributed Computing (PODC) 2017.
[arXiv]

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer
International Colloquium on Automata, Languages, and Programming (ICALP) 2017.
[DOI]

Approximating Small Balanced Vertex Separators in Almost Linear Time
Sebastian Brandt and Roger Wattenhofer
Algorithms and Data Structures Symposium (WADS) 2017.
Best Student Paper Award at WADS'17
[pdf]

Collaboration Without Communication: Evacuating Two Robots from a Disk
Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, and Roger Wattenhofer
International Conference on Algorithms and Complexity (CIAC) 2017.
[pdf]

Wireless Evacuation on m Rays with k Searchers
Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, and Roger Wattenhofer
International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2017.
[DOI]

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
ACM Symposium on Theory of Computing (STOC) 2016.
[arXiv]

On Consistent Migration of Flows in SDNs
Sebastian Brandt, Klaus-Tycho Förster, and Roger Wattenhofer
IEEE International Conference on Computer Communications (INFOCOM) 2016.
[DOI]

Augmenting Anycast Network Flows
Sebastian Brandt, Klaus-Tycho Förster, and Roger Wattenhofer
International Conference on Distributed Computing and Networking (ICDCN) 2016.
[DOI]

Toehold DNA Languages are Regular
Sebastian Brandt, Nicolas Mattia, Jochen Seidel, and Roger Wattenhofer
International Symposium on Algorithms and Computation (ISAAC) 2015.
[pdf]



Journal Publications

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
Sebastian Brandt, Manuela Fischer, and Jara Uitto
Theoretical Computer Science, 2021.
[DOI]

Almost Global Problems in the LOCAL Model
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela
Distibuted Computing, 2020.
[DOI]

A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration
Sebastian Brandt, Jara Uitto, and Roger Wattenhofer
Distibuted Computing, 2020.
[DOI]

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer
Theoretical Computer Science, 2020.
[DOI]

Wireless Evacuation on m Rays with k Searchers
Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, and Roger Wattenhofer
Theoretical Computer Science, 2020.
[DOI]

Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs
Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, and Roger Wattenhofer
Theoretical Computer Science, 2020.
[DOI]

Approximating Small Balanced Vertex Separators in Almost Linear Time
Sebastian Brandt and Roger Wattenhofer
Algorithmica, 2019.
[DOI]

Augmenting Flows for the Consistent Migration of Multi-Commodity Single-Destination Flows in SDNs
Sebastian Brandt, Klaus-Tycho Foerster, and Roger Wattenhofer
Pervasive and Mobile Computing, 2017.
[DOI]

Contact Information

Sebastian Brandt
Institute of Theoretical Computer Science, ETH Zurich
CAB G 32.2
Universitätstrasse 6
8092 Zurich, Switzerland

+41 44 632 72 37

brandts at ethz.ch