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…