1 citations · 2 across the 15 of their papers we have counts for
6 papers · 2 filters
Improved Distributed Fractional Coloring Algorithms
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
We prove new bounds on the distributed fractional coloring problem in the LOCAL model. Fractional -colorings can be understood as multicolorings as follows. For some natural num…
Distributed -Coloring Plays Hide-and-Seek
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We prove several new tight distributed lower bounds for classic symmetry breaking graph problems. As a basic tool, we first provide a new insightful proof that any deterministic di…
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…
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bou…
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…
Local Mending
Alkida Balliu, Juho Hirvonen, Darya Melnyk +3
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far o…