18 citations · 27 across the 26 of their papers we have counts for
5 papers · 2 filters
Optimal Deterministic Massively Parallel Connectivity on Forests
Alkida Balliu, Rustam Latypov, Yannic Maus +2
We show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent b…
Exponential Speedup Over Locality in MPC with Optimal Memory
Alkida Balliu, Sebastian Brandt, Manuela Fischer +4
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example p…
Node and Edge Averaged Complexities of Local Graph Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +1
The node-averaged complexity of a distributed algorithm running on a graph is the average over the times at which the nodes of finish their computation and commit…
Distributed Edge Coloring in Time Polylogarithmic in
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main resu…
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)…