9 papers
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +3
One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model u…
Deterministic Distributed Algorithms and Measurable Combinatorics on -Regular Forests
Sebastian Brandt, Yi-Jun Chang, Jan GrebÃk +3
We investigate the connections between the fields of distributed computing and measurable combinatorics by considering complexity classes of locally checkable labeling problems on…
On the Complexity of Distributed Edge Coloring and Orientation Problems
Sebastian Brandt, Fabian Kuhn, Zahra Parsaeian
Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed gra…
On the Universality of Round Elimination Fixed Points
Alkida Balliu, Sebastian Brandt, Ole Gabsdil +2
Recent work on distributed graph algorithms [e.g. STOC 2022, ITCS 2022, PODC 2020] has drawn attention to the following open question: are round elimination fixed points a universa…
Distributed Computation with Local Advice
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +4
In this work we study local computation with advice: the goal is to solve a graph problem with a distributed algorithm in communication rounds, for some function t…
Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prio…