
Locally Checkable Labelings with Small Messages
A rich line of work has been addressing the computational complexity of ...
read it

Locality in Online Algorithms
Online algorithms make decisions based on past inputs. In general, the d...
read it

Locally Checkable Problems in Rooted Trees
Consider any locally checkable labeling problem Π in rooted regular tree...
read it

Local Mending
In this work we introduce the graphtheoretic notion of mendability: for...
read it

Efficient LoadBalancing through Distributed Token Dropping
We introduce a new graph problem, the token dropping game, and we show h...
read it

Distributed graph problems through an automatatheoretic lens
We study the following algorithm synthesis question: given the descripti...
read it

Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
read it

Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Consider a graph problem that is locally checkable but not locally solva...
read it

Locality of notsoweak coloring
Many graph problems are locally checkable: a solution is globally feasib...
read it

How much does randomness help with locally checkable problems?
Locally checkable labeling problems (LCLs) are distributed graph problem...
read it

Lower bounds for maximal matchings and maximal independent sets
There are distributed graph algorithms for finding maximal matchings and...
read it

On the Power of Preprocessing in Decentralized Network Optimization
As communication networks are growing at a fast pace, the need for more ...
read it

The distributed complexity of locally checkable problems on paths is decidable
Consider a computer network that consists of a path with n nodes. The no...
read it

Hardness of minimal symmetry breaking in distributed computing
A graph is weakly 2colored if the nodes are labeled with colors black a...
read it

Almost Global Problems in the LOCAL Model
The landscape of the distributed time complexity is nowadays wellunders...
read it

Distributed Recoloring
Given two colorings of a graph, we consider the following problem: can w...
read it

New Classes of Distributed Time Complexity
A number of recent papers  e.g. Brandt et al. (STOC 2016), Chang et al...
read it
Jukka Suomela
is this you? claim profile