6 papers · 1 filter
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Mohsen Ghaffari, Christoph Grunau
This paper presents massively parallel computation (MPC) algorithms in the strongly sublinear memory regime (aka, scalable MPC) for orienting and coloring graphs as a function of i…
Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
Mohsen Ghaffari, Christoph Grunau
Derandomization is one of the classic topics studied in the theory of parallel computations, dating back to the early 1980s. Despite much work, all known techniques lead to determi…
Dynamic O(arboricity) coloring in polylogarithmic worst-case time
Mohsen Ghaffari, Christoph Grunau
A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic algorithms for coloring sparse graphs, concretely as a function of the arboricity alpha of the input graph. T…
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Mohsen Ghaffari, Christoph Grunau
This paper improves and in two cases nearly settles, up to logarithmically lower-order factors, the deterministic complexity of some of the most central problems in distributed gra…
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari, Christoph Grunau
We present an efficient parallel derandomization method for randomized algorithms that rely on concentrations such as the Chernoff bound. This settles a classic problem in parallel…
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein…