92 citations · 480 across the 54 of their papers we have counts for
5 papers · 1 filter
Classification of distributed binary labeling problems
Alkida Balliu, Sebastian Brandt, Yuval Efron +4
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable…
Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Will Rosenbaum, Jukka Suomela
Consider a graph problem that is locally checkable but not locally solvable: given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but t…
Locality of not-so-weak coloring
Alkida Balliu, Juho Hirvonen, Christoph Lenzen +2
Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally…
How much does randomness help with locally checkable problems?
Alkida Balliu, Sebastian Brandt, Dennis Olivetti +1
Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. V…
Lower bounds for maximal matchings and maximal independent sets
Alkida Balliu, Sebastian Brandt, Juho Hirvonen +3
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in communication rounds; here is the number of nodes and …