18 citations · 22 across the 23 of their papers we have counts for
3 papers · 1 filter
The distributed complexity of locally checkable problems on paths is decidable
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
Consider a computer network that consists of a path with nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a consta…
Hardness of minimal symmetry breaking in distributed computing
Alkida Balliu, Juho Hirvonen, Dennis Olivetti +1
A graph is weakly -colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we…
Almost Global Problems in the LOCAL Model
Alkida Balliu, Sebastian Brandt, Dennis Olivetti +1
The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally…