5 papers
Sparse Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Juho Hirvonen, Janne H. Korhonen +2
We study matrix multiplication in the low-bandwidth model: There are computers, and we need to compute the product of two matrices. Initially computer knows ro…
Efficient Classification of Locally Checkable Problems in Regular Trees
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)…
Sinkless Orientation Made Simple
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn +9
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distribut…
Locally Checkable Problems in Rooted Trees
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +4
Consider any locally checkable labeling problem in rooted regular trees: there is a finite set of labels , and for each label we specify what are permitted label c…
Distributed graph problems through an automata-theoretic lens
Yi-Jun Chang, Jan Studený, Jukka Suomela
The locality of a graph problem is the smallest distance such that each node can choose its own part of the solution based on its radius- neighborhood. In many settings, a g…