3 papers
cs.DC2026
Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs
Marc Fuchs, Diana Ghinea, Zahra Parsaeian +1
Approximate Agreement () is a fundamental primitive that, even in the presence of Byzantine faults, allows honest parties to obtain close (but not necessarily identic…
cs.DS2025
On the Complexity of Distributed Edge Coloring and Orientation Problems
Sebastian Brandt, Fabian Kuhn, Zahra Parsaeian
Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed gra…
cs.DS2025
An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the -Means Problem
Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian
In this paper, we present an efficient massively parallel approximation algorithm for the -means problem. Specifically, we provide an MPC algorithm that computes a constant-fact…