Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set

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 deterministic algorithms that are not work-efficient. For instance, for the well-studied problem of maximal independent set -- e.g., [Karp, Wigderson STOC'84; Luby STOC' 85; Luby FOCS'88] -- state-of-the-art deterministic algorithms require at least m · poly(log n) work, where m and n denote the number of edges and vertices. Hence, these deterministic algorithms will remain slower than their trivial sequential counterparts unless we have at least poly(log n) processors. In this paper, we present a generic parallel derandomization technique that moves exponentially closer to work-efficiency. The method iteratively rounds fractional solutions representing the randomized assignments to integral solutions that provide deterministic assignments, while maintaining certain linear or quadratic objective functions, and in an essentially work-efficient manner. As example end-results, we use this technique to obtain deterministic algorithms with m · poly(log log n) work and poly(log n) depth for problems such as maximal independent set, maximal matching, and hitting set.