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 focuses on the study of distributed algorithms, in particular the limitations imposed on them by locality. I am also interested in various more-or-less related topics such as biologically-inspired algorithms, mobile agents, or massively parallel computation.



Manuscripts

Distributed Lower Bounds for Ruling Sets
Alkida Balliu, Sebastian Brandt, and Dennis Olivetti
[arXiv]

Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
Sebastian Brandt and Dennis Olivetti
[arXiv]

Classification of Distributed Binary Labeling Problems
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela
[arXiv]

How Much Does Randomness Help with Locally Checkable Problems?
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela
[arXiv]



Publications

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]

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