6 citations · 27 across the 32 of their papers we have counts for
5 papers · 1 filter
Distributed Vertex Cover Reconfiguration
Keren Censor-Hillel, Yannic Maus, Shahar Romem-Peled +1
Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most r…
Efficient CONGEST Algorithms for the Lovasz Local Lemma
Yannic Maus, Jara Uitto
We present a poly time randomized CONGEST algorithm for a natural class of Lovasz Local Lemma (LLL) instances on constant degree graphs. This implies, among other thi…
Locally Checkable Labelings with Small Messages
Alkida Balliu, Keren Censor-Hillel, Yannic Maus +2
A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we s…
Distributed Graph Coloring Made Easy
Yannic Maus
In this paper we present a deterministic CONGEST algorithm to compute an -vertex coloring in rounds, where is the maximum degree of the network graph a…
Near-Optimal Scheduling in the Congested Clique
Keren Censor-Hillel, Yannic Maus, Volodymyr Polosukhin
This paper provides three nearly-optimal algorithms for scheduling jobs in the model. First, we present a deterministic scheduling algorithm that runs in $O(\…