10 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…
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 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…
Towards Fully Automatic Distributed Lower Bounds
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
In the past few years, a successful line of research has lead to lower bounds for several fundamental local graph problems in the distributed setting. These results were obtained v…
Completing the Node-Averaged Complexity Landscape of LCLs on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of res…
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 tha…
Tight Lower Bounds in the Supported LOCAL Model
Alkida Balliu, Thomas Boudier, Sebastian Brandt +1
We study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start…
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…
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We study connections between distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics in the context of regular trees. We extend the Borel det…