Sebastian Brandt

109 papers A* 31A 13B 6C 1Misc 1Journal 57

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	A Post-Quantum Lower Bound for the Distributed Lovasz Local Lemma. SODA Sebastian Brandt, Tim Göttlicher
2026	A*	`conf`	Faster Distributed Δ-Coloring via a Reduction to MIS. SODA Yann Bourreau, Sebastian Brandt, Alexandre Nolin
2026	A*	`conf`	On the Universality of Round Elimination Fixed Points. SODA Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela
2025	J	`jnl`	A Post-Quantum Lower Bound for the Distributed Lovász Local Lemma. CoRR Sebastian Brandt, Tim Göttlicher
2025	A	`conf`	Distributed Computation with Local Advice. DISC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
2025	A*	`conf`	Distributed Quantum Advantage for Local Problems. STOC Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren
2025	J	`jnl`	Exponential speedup over locality in MPC with optimal memory. Distributed Comput. Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2025	A*	`conf`	Faster Distributed Δ-Coloring via Ruling Subgraphs. STOC Yann Bourreau, Sebastian Brandt, Alexandre Nolin
2025	J	`jnl`	Faster Distributed Δ-Coloring via Ruling Subgraphs. CoRR Yann Bourreau, Sebastian Brandt, Alexandre Nolin
2025	J	`jnl`	Faster Distributed Δ-Coloring via a Reduction to MIS. CoRR Yann Bourreau, Sebastian Brandt, Alexandre Nolin
2025	B	`conf`	On the Complexity of Distributed Edge Coloring and Orientation Problems. OPODIS Sebastian Brandt, Fabian Kuhn, Zahra Parsaeian
2025	J	`jnl`	On the Complexity of Distributed Edge Coloring and Orientation Problems. CoRR Sebastian Brandt, Fabian Kuhn, Zahra Parsaeian
2025	A*	`conf`	On the Locality of Hall's Theorem. SODA Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, Jara Uitto
2025	J	`jnl`	On the Locality of Hall's Theorem. CoRR Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, Jara Uitto
2025	J	`jnl`	On the Universality of Round Elimination Fixed Points. CoRR Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela
2025	A	`conf`	Towards Fully Automatic Distributed Lower Bounds. DISC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Joonatan Saarhelo
2025	A*	`conf`	Towards Optimal Deterministic LOCAL Algorithms on Trees. PODC Sebastian Brandt, Ananth Narayanan
2025	J	`jnl`	Towards Optimal Deterministic LOCAL Algorithms on Trees. CoRR Sebastian Brandt, Ananth Narayanan
2024	A*	`conf`	Brief Announcement: Local Advice and Local Decompression. PODC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
2024	A*	`conf`	Completing the Node-Averaged Complexity Landscape of LCLs on Trees. PODC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2024	J	`jnl`	Completing the Node-Averaged Complexity Landscape of LCLs on Trees. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2024	J	`jnl`	Distributed Quantum Advantage for Local Problems. CoRR Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren
2024	J	`jnl`	Local Advice and Local Decompression. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
2024	A*	`conf`	Tight Lower Bounds in the Supported LOCAL Model. PODC Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti
2024	J	`jnl`	Tight Lower Bounds in the Supported LOCAL Model. CoRR Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti
2024	J	`jnl`	Towards Fully Automatic Distributed Lower Bounds. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Joonatan Saarhelo
2023	A*	`conf`	Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. SODA Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2023	J	`jnl`	Locally checkable problems in rooted trees. Distributed Comput. Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
2023	J	`jnl`	Location Estimation and Recovery using 5G Positioning: Thwarting GNSS Spoofing Attacks. CoRR Aneet Kumar Dutta, Sebastian Brandt, Mridula Singh
2023	A	`conf`	On the Node-Averaged Complexity of Locally Checkable Problems on Trees. DISC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2023	J	`jnl`	On the Node-Averaged Complexity of Locally Checkable Problems on Trees. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2022	J	`jnl`	Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees. CoRR Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2022	A*	`conf`	Distributed Edge Coloring in Time Polylogarithmic in Δ. PODC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022	J	`jnl`	Distributed Edge Coloring in Time Polylogarithmic in Δ. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022	J	`jnl`	Distributed Lower Bounds for Ruling Sets. SIAM J. Comput. Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2022	J	`jnl`	Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022	A*	`conf`	Distributed ∆-coloring plays hide-and-seek. STOC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022	J	`jnl`	Efficient Classification of Local Problems in Regular Trees. CoRR Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
2022	A	`conf`	Efficient Classification of Locally Checkable Problems in Regular Trees. DISC Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
2022	J	`jnl`	Exponential Speedup Over Locality in MPC with Optimal Memory. CoRR Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2022	A	`conf`	Exponential Speedup over Locality in MPC with Optimal Memory. DISC Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2022	A	`conf`	Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. ITCS Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2022	A*	`conf`	The Landscape of Distributed Complexities on Trees and Beyond. PODC Christoph Grunau, Václav Rozhon, Sebastian Brandt
2022	J	`jnl`	The Landscape of Distributed Complexities on Trees and Beyond. CoRR Christoph Grunau, Václav Rozhon, Sebastian Brandt
2021	J	`jnl`	Almost global problems in the LOCAL model. Distributed Comput. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2021	J	`jnl`	Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory. Theor. Comput. Sci. Sebastian Brandt, Manuela Fischer, Jara Uitto
2021	A	`conf`	Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. DISC Sebastian Brandt, Rustam Latypov, Jara Uitto
2021	J	`jnl`	Distributed Δ-Coloring Plays Hide-and-Seek. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2021	B	`conf`	Efficient Load-Balancing through Distributed Token Dropping. SPAA Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto
2021	A*	`conf`	Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. PODC Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2021	J	`jnl`	Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. CoRR Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2021	J	`jnl`	Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. CoRR Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2021	A*	`conf`	Locally Checkable Problems in Rooted Trees. PODC Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
2021	J	`jnl`	Locally Checkable Problems in Rooted Trees. CoRR Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
2021	J	`jnl`	Lower Bounds for Maximal Matchings and Maximal Independent Sets. J. ACM Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2021	J	`jnl`	Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. CoRR Sebastian Brandt, Rustam Latypov, Jara Uitto
2021	J	`jnl`	On Homomorphism Graphs. CoRR Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2021	A*	`conf`	The Randomized Local Computation Complexity of the Lovász Local Lemma. PODC Sebastian Brandt, Christoph Grunau, Václav Rozhon
2021	J	`jnl`	The randomized local computation complexity of the Lovász local lemma. CoRR Sebastian Brandt, Christoph Grunau, Václav Rozhon
2020	J	`jnl`	A tight lower bound for semi-synchronous collaborative grid exploration. Distributed Comput. Sebastian Brandt, Jara Uitto, Roger Wattenhofer
2020	J	`jnl`	A tight lower bound for the capture time of the Cops and Robbers game. Theor. Comput. Sci. Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer
2020	A*	`conf`	Brief Announcement: Classification of Distributed Binary Labeling Problems. PODC Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
2020	A	`conf`	Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping. DISC Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto
2020	A	`conf`	Classification of Distributed Binary Labeling Problems. DISC Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
2020	A*	`conf`	Distributed Lower Bounds for Ruling Sets. FOCS Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2020	J	`jnl`	Distributed Lower Bounds for Ruling Sets. CoRR Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2020	J	`jnl`	Efficient Load-Balancing through Distributed Token Dropping. CoRR Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto
2020	A*	`conf`	Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. PODC Sebastian Brandt, Christoph Grunau, Václav Rozhon
2020	J	`jnl`	Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. CoRR Sebastian Brandt, Christoph Grunau, Václav Rozhon
2020	A*	`conf`	How much does randomness help with locally checkable problems? PODC Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2020	J	`jnl`	Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs. Theor. Comput. Sci. Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer
2020	A	`conf`	Tight Bounds for Deterministic High-Dimensional Grid Exploration. DISC Sebastian Brandt, Julian Portmann, Jara Uitto
2020	J	`jnl`	Tight Bounds for Deterministic High-Dimensional Grid Exploration. CoRR Sebastian Brandt, Julian Portmann, Jara Uitto
2020	A*	`conf`	Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants. PODC Sebastian Brandt, Dennis Olivetti
2020	J	`jnl`	Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants. CoRR Sebastian Brandt, Dennis Olivetti
2020	J	`jnl`	Wireless evacuation on Theor. Comput. Sci. Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, Roger Wattenhofer
2019	A*	`conf`	A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. PODC Sebastian Brandt, Yannic Maus, Jara Uitto
2019	J	`jnl`	A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. CoRR Sebastian Brandt, Yannic Maus, Jara Uitto
2019	A*	`conf`	An Automatic Speedup Theorem for Distributed Problems. PODC Sebastian Brandt
2019	J	`jnl`	An Automatic Speedup Theorem for Distributed Problems. CoRR Sebastian Brandt
2019	J	`jnl`	Approximating Small Balanced Vertex Separators in Almost Linear Time. Algorithmica Sebastian Brandt, Roger Wattenhofer
2019	B	`conf`	Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory. SIROCCO Sebastian Brandt, Manuela Fischer, Jara Uitto
2019	J	`jnl`	Classification of distributed binary labeling problems. CoRR Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
2019	J	`jnl`	How much does randomness help with locally checkable problems? CoRR Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2019	A*	`conf`	Lower Bounds for Maximal Matchings and Maximal Independent Sets. FOCS Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2019	J	`jnl`	Lower bounds for maximal matchings and maximal independent sets. CoRR Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2019	A*	`conf`	Massively Parallel Computation of Matching and MIS in Sparse Graphs. PODC Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, Jara Uitto
2019	J	`jnl`	Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs. CoRR Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer
2019	J	`jnl`	SIROCCO 2019 Review. SIGACT News Sebastian Brandt, Manuela Fischer, Jara Uitto
2019	A*	`conf`	The Distributed Complexity of Locally Checkable Problems on Paths is Decidable. PODC Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2018	A	`conf`	A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration. DISC Sebastian Brandt, Jara Uitto, Roger Wattenhofer
2018	A	`conf`	Almost Global Problems in the LOCAL Model. DISC Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2018	J	`jnl`	Almost Global Problems in the LOCAL Model. CoRR Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2018	A	`conf`	Fine-grained Lower Bounds on Cops and Robbers. ESA Sebastian Brandt, Seth Pettie, Jara Uitto
2018	J	`jnl`	Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. CoRR Sebastian Brandt, Manuela Fischer, Jara Uitto
2018	J	`jnl`	The distributed complexity of locally checkable problems on paths is decidable. CoRR Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2017	A*	`conf`	A Tight Lower Bound for the Capture Time of the Cops and Robbers Game. ICALP Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer
2017	B	`conf`	Approximating Small Balanced Vertex Separators in Almost Linear Time. WADS Sebastian Brandt, Roger Wattenhofer
2017	J	`jnl`	Augmenting flows for the consistent migration of multi-commodity single-destination flows in SDNs. Pervasive Mob. Comput. Sebastian Brandt, Klaus-Tycho Foerster, Roger Wattenhofer
2017	C	`conf`	Collaboration Without Communication: Evacuating Two Robots from a Disk. CIAC Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, Roger Wattenhofer
2017	A*	`conf`	LCL Problems on Grids. PODC Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemyslaw Uznanski
2017	J	`jnl`	LCL problems on grids. CoRR Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemyslaw Uznanski
2017	J	`jnl`	Tight Bounds for Asynchronous Collaborative Grid Exploration. CoRR Sebastian Brandt, Jara Uitto, Roger Wattenhofer
2017	B	`conf`	Wireless Evacuation on m Rays with k Searchers. SIROCCO Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, Roger Wattenhofer
2016	A*	`conf`	A lower bound for the distributed Lovász local lemma. STOC Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto
2016	Misc	`conf`	Augmenting anycast network flows. ICDCN Sebastian Brandt, Klaus-Tycho Förster, Roger Wattenhofer
2016	A*	`conf`	On consistent migration of flows in SDNs. INFOCOM Sebastian Brandt, Klaus-Tycho Förster, Roger Wattenhofer
2015	J	`jnl`	A Lower Bound for the Distributed Lovász Local Lemma. CoRR Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto
2015	B	`conf`	Toehold DNA Languages are Regular. ISAAC Sebastian Brandt, Nicolas Mattia, Jochen Seidel, Roger Wattenhofer