6 papers
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…
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…
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…
Massively Parallel Ruling Set Made Deterministic
Jeff Giliberti, Zahra Parsaeian
We study the deterministic complexity of the -Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory. Linear MPC…
Laminar Matroid Secretary: Greedy Strikes Back
Zhiyi Huang, Zahra Parsaeian, Zixuan Zhu
We show that a simple greedy algorithm is probability-competitive for the Laminar Matroid Secretary Problem, improving the -competitive algorithm ba…
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertice…