research
∙
07/18/2023
No distributed quantum advantage for approximate graph coloring
We give an almost complete characterization of the hardness of c-colorin...
share
research
∙
05/12/2023
Distributed derandomization revisited
One of the cornerstones of the distributed complexity theory is the dera...
research
∙
05/05/2023
Fast Dynamic Programming in Trees in the MPC Model
We present a deterministic algorithm for solving a wide range of dynamic...
research
∙
03/09/2023
Distributed Half-Integral Matching and Beyond
By prior work, it is known that any distributed graph algorithm that fin...
research
∙
09/12/2022
Mending Partial Solutions with Few Changes
In this paper, we study the notion of mending, i.e. given a partial solu...
research
∙
03/02/2022
Sparse matrix multiplication in the low-bandwidth model
We study matrix multiplication in the low-bandwidth model: There are n c...
research
∙
02/17/2022
Efficient Classification of Local Problems in Regular Trees
We give practical, efficient algorithms that automatically determine the...
research
∙
09/14/2021
Online Algorithms with Lookaround
We introduce a new model of computation: the online LOCAL model (OLOCAL)...
research
∙
08/05/2021
Sinkless orientation is hard also in the supported LOCAL model
We show that any algorithm that solves the sinkless orientation problem ...
research
∙
05/12/2021
Locally Checkable Labelings with Small Messages
A rich line of work has been addressing the computational complexity of ...
research
∙
02/18/2021
Locality in Online Algorithms
Online algorithms make decisions based on past inputs. In general, the d...
research
∙
02/18/2021
Locally Checkable Problems in Rooted Trees
Consider any locally checkable labeling problem Π in rooted regular tree...
research
∙
02/17/2021
Local Mending
In this work we introduce the graph-theoretic notion of mendability: for...
research
∙
05/15/2020
Efficient Load-Balancing through Distributed Token Dropping
We introduce a new graph problem, the token dropping game, and we show h...
research
∙
02/18/2020
Distributed graph problems through an automata-theoretic lens
We study the following algorithm synthesis question: given the descripti...
research
∙
11/29/2019
Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
research
∙
07/18/2019
Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Consider a graph problem that is locally checkable but not locally solva...
research
∙
04/11/2019
Locality of not-so-weak coloring
Many graph problems are locally checkable: a solution is globally feasib...
research
∙
02/18/2019
How much does randomness help with locally checkable problems?
Locally checkable labeling problems (LCLs) are distributed graph problem...
research
∙
01/08/2019
Lower bounds for maximal matchings and maximal independent sets
There are distributed graph algorithms for finding maximal matchings and...
research
∙
12/03/2018
On the Power of Preprocessing in Decentralized Network Optimization
As communication networks are growing at a fast pace, the need for more ...
research
∙
11/05/2018
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...
research
∙
11/05/2018
Hardness of minimal symmetry breaking in distributed computing
A graph is weakly 2-colored if the nodes are labeled with colors black a...
research
∙
05/12/2018
Almost Global Problems in the LOCAL Model
The landscape of the distributed time complexity is nowadays well-unders...
research
∙
02/19/2018
Distributed Recoloring
Given two colorings of a graph, we consider the following problem: can w...
research
∙
11/06/2017