2 papers
cs.DS2026
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…
cs.DS2024
A Cut-Matching Game for Constant-Hop Expanders
Bernhard Haeupler, Jonas Huebotter, Mohsen Ghaffari
This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders. Constant-hop expanders are a s…