8 papers
True Work-Efficiency in Parallel Derandomization
Mohsen Ghaffari, Cheng Jiang
A longstanding limitation of known techniques for parallel derandomization was that they incurred at least polylogarithmic overhead in work. For instance, for fundamental and frequ…
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…
Fast Broadcast in Highly Connected Networks
Shashwat Chandra, Yi-Jun Chang, Michal Dory +2
We revisit the classic broadcast problem, wherein we have messages, each composed of bits, distributed arbitrarily across a network. The objective is to broadcast…
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…