Sebastian Brandt

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 88

Top Topics

Massively Parallel

Labeling Problems

Top Venues

Theor. Comput. Sci.

Publications

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
Completing the Node-Averaged Complexity Landscape of LCLs on Trees. PODC (2024)
Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti
Tight Lower Bounds in the Supported LOCAL Model. PODC (2024)
Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti
Tight Lower Bounds in the Supported LOCAL Model. CoRR (2024)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
Completing the Node-Averaged Complexity Landscape of LCLs on Trees. CoRR (2024)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
Brief Announcement: Local Advice and Local Decompression. PODC (2024)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
Local Advice and Local Decompression. CoRR (2024)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
Locally checkable problems in rooted trees. Distributed Comput. 36 (3) (2023)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. SODA (2023)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
On the Node-Averaged Complexity of Locally Checkable Problems on Trees. DISC (2023)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
On the Node-Averaged Complexity of Locally Checkable Problems on Trees. CoRR (2023)
Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. ITCS (2022)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Distributed ∆-coloring plays hide-and-seek. STOC (2022)
Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees. CoRR (2022)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
Distributed Lower Bounds for Ruling Sets. SIAM J. Comput. 51 (1) (2022)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
Efficient Classification of Local Problems in Regular Trees. CoRR (2022)
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
Exponential Speedup Over Locality in MPC with Optimal Memory. CoRR (2022)
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
Exponential Speedup over Locality in MPC with Optimal Memory. DISC (2022)
Christoph Grunau, Václav Rozhon, Sebastian Brandt
The Landscape of Distributed Complexities on Trees and Beyond. CoRR (2022)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. CoRR (2022)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Distributed Edge Coloring in Time Polylogarithmic in Δ. CoRR (2022)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
Efficient Classification of Locally Checkable Problems in Regular Trees. DISC (2022)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Distributed Edge Coloring in Time Polylogarithmic in Δ. PODC (2022)
Christoph Grunau, Václav Rozhon, Sebastian Brandt
The Landscape of Distributed Complexities on Trees and Beyond. PODC (2022)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. PODC (2021)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
Locally Checkable Problems in Rooted Trees. PODC (2021)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Distributed Δ-Coloring Plays Hide-and-Seek. CoRR (2021)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
Locally Checkable Problems in Rooted Trees. CoRR (2021)
Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. CoRR (2021)
Sebastian Brandt, Christoph Grunau, Václav Rozhon
The randomized local computation complexity of the Lovász local lemma. CoRR (2021)
Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto
Efficient Load-Balancing through Distributed Token Dropping. SPAA (2021)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
Almost global problems in the LOCAL model. Distributed Comput. 34 (4) (2021)
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
Lower Bounds for Maximal Matchings and Maximal Independent Sets. J. ACM 68 (5) (2021)
Sebastian Brandt, Christoph Grunau, Václav Rozhon
The Randomized Local Computation Complexity of the Lovász Local Lemma. PODC (2021)
Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
On Homomorphism Graphs. CoRR (2021)
Sebastian Brandt, Manuela Fischer, Jara Uitto
Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory. Theor. Comput. Sci. 849 (2021)
Sebastian Brandt, Rustam Latypov, Jara Uitto
Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. DISC (2021)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. CoRR (2021)
Sebastian Brandt, Rustam Latypov, Jara Uitto
Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. CoRR (2021)
Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, Roger Wattenhofer
searchers. Theor. Comput. Sci. 811 (2020)
Sebastian Brandt, Dennis Olivetti
Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants. CoRR (2020)
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
Brief Announcement: Classification of Distributed Binary Labeling Problems. PODC (2020)
Sebastian Brandt, Julian Portmann, Jara Uitto
Tight Bounds for Deterministic High-Dimensional Grid Exploration. DISC (2020)
Sebastian Brandt, Jara Uitto, Roger Wattenhofer
A tight lower bound for semi-synchronous collaborative grid exploration. Distributed Comput. 33 (6) (2020)
Sebastian Brandt, Dennis Olivetti
Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants. PODC (2020)
Sebastian Brandt, Christoph Grunau, Václav Rozhon
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. CoRR (2020)
Sebastian Brandt, Christoph Grunau, Václav Rozhon
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. PODC (2020)
Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto
Efficient Load-Balancing through Distributed Token Dropping. CoRR (2020)
Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer
A tight lower bound for the capture time of the Cops and Robbers game. Theor. Comput. Sci. 839 (2020)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
How much does randomness help with locally checkable problems? PODC (2020)
Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto
Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping. DISC (2020)
Sebastian Brandt, Julian Portmann, Jara Uitto
Tight Bounds for Deterministic High-Dimensional Grid Exploration. CoRR (2020)
Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer
Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs. Theor. Comput. Sci. 839 (2020)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
Distributed Lower Bounds for Ruling Sets. FOCS (2020)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
Distributed Lower Bounds for Ruling Sets. CoRR (2020)
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
Classification of Distributed Binary Labeling Problems. DISC (2020)
Sebastian Brandt
An Automatic Speedup Theorem for Distributed Problems. PODC (2019)
Sebastian Brandt
An Automatic Speedup Theorem for Distributed Problems. CoRR (2019)
Sebastian Brandt, Roger Wattenhofer
Approximating Small Balanced Vertex Separators in Almost Linear Time. Algorithmica 81 (10) (2019)
Sebastian Brandt, Manuela Fischer, Jara Uitto
SIROCCO 2019 Review. SIGACT News 50 (4) (2019)
Sebastian Brandt, Manuela Fischer, Jara Uitto
Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory. SIROCCO (2019)
Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer
Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs. CoRR (2019)
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, Jara Uitto
Massively Parallel Computation of Matching and MIS in Sparse Graphs. PODC (2019)
Sebastian Brandt, Yannic Maus, Jara Uitto
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. PODC (2019)
Sebastian Brandt, Yannic Maus, Jara Uitto
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. CoRR (2019)
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
Classification of distributed binary labeling problems. CoRR (2019)
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
Lower bounds for maximal matchings and maximal independent sets. CoRR (2019)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
The Distributed Complexity of Locally Checkable Problems on Paths is Decidable. PODC (2019)
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
Lower Bounds for Maximal Matchings and Maximal Independent Sets. FOCS (2019)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
How much does randomness help with locally checkable problems? CoRR (2019)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
Almost Global Problems in the LOCAL Model. DISC (2018)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
The distributed complexity of locally checkable problems on paths is decidable. CoRR (2018)
Sebastian Brandt, Jara Uitto, Roger Wattenhofer
A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration. DISC (2018)
Sebastian Brandt, Manuela Fischer, Jara Uitto
Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. CoRR (2018)
Sebastian Brandt, Seth Pettie, Jara Uitto
Fine-grained Lower Bounds on Cops and Robbers. ESA (2018)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
Almost Global Problems in the LOCAL Model. CoRR (2018)
Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game. ICALP (2017)
Sebastian Brandt, Jara Uitto, Roger Wattenhofer
Tight Bounds for Asynchronous Collaborative Grid Exploration. CoRR (2017)
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemyslaw Uznanski
LCL Problems on Grids. PODC (2017)
Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, Roger Wattenhofer
Collaboration Without Communication: Evacuating Two Robots from a Disk. CIAC (2017)
Sebastian Brandt, Klaus-Tycho Foerster, Roger Wattenhofer
Augmenting flows for the consistent migration of multi-commodity single-destination flows in SDNs. Pervasive Mob. Comput. 36 (2017)
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemyslaw Uznanski
LCL problems on grids. CoRR (2017)
Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, Roger Wattenhofer
Wireless Evacuation on m Rays with k Searchers. SIROCCO (2017)
Sebastian Brandt, Roger Wattenhofer
Approximating Small Balanced Vertex Separators in Almost Linear Time. WADS (2017)
Sebastian Brandt, Klaus-Tycho Förster, Roger Wattenhofer
Augmenting anycast network flows. ICDCN (2016)
Sebastian Brandt, Klaus-Tycho Förster, Roger Wattenhofer
On consistent migration of flows in SDNs. INFOCOM (2016)
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto
A lower bound for the distributed Lovász local lemma. STOC (2016)
Sebastian Brandt, Nicolas Mattia, Jochen Seidel, Roger Wattenhofer
Toehold DNA Languages are Regular. ISAAC (2015)
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto
A Lower Bound for the Distributed Lovász Local Lemma. CoRR (2015)