Showing 2026Show all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…