6 citations · 27 across the 32 of their papers we have counts for
9 papers · 1 filter
LOCAL LLL in Rounds
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We provide a -round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion , for a sufficiently l…
Distributed Symmetry Breaking on Hyperbolic Random Graphs
Yannic Maus, Janosch Ruff, Sonia Simons +1
Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative…
Robust Shattering Arguments
Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus +1
Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that lar…
Deterministic Distance Approximation in MPC via Improved Hitting Sets
Kyungjin Cho, Michal Dory, Yannic Maus +1
In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we si…
Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity
Malte Baumecker, Rustam Latypov, Yannic Maus +1
Given a graph , a -ruling set is a subset of nodes that is independent, and each node in is at distance at most from some node in . In this pa…
Distributed Santa Claus via Global Rounding
Tijn de Vos, Leo Wennmann, Malte Baumecker +2
In this paper, we initiate the study of a new class of problems in the CONGEST model: Mixed packing and covering linear programs (LP). Previously, the design of optimization algori…