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

Mohsen Ghaffari, Christoph Grunau · 2025

Read Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set by Mohsen Ghaffari, Christoph Grunau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15700.txt.

Introduction

Mohsen Ghaffari and Christoph Grunau present a study from twenty twenty-five on making parallel algorithms free of chance without wasting work. Known ways to strip chance from parallel code cost far more work than the plain serial code. For the classic task of a maximal set of points with no shared edge, this gap has stood since the early years of the field.

Their method rounds shared, split values to whole picks step by step. It keeps key sums near their marks while it does so, at near serial work cost. They use it for the set task, a pairing task, and a hitting set task. Each gets near true work savings with shallow depth. The pair frame it as a general tool, not a one case fix.

Catalog record

CREATORMohsen Ghaffari, Christoph Grunau
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15700

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set Mohsen Ghaffari, Christoph Grunau Abstract 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 ) m\cdot\operatorname{poly}(\log n) work, where m m and n 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 ) \operatorname{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 ) m\cdot\operatorname{poly}(\log\log n) work and poly ⁡ ( log ⁡ n ) \operatorname{poly}(\log n) depth for problems such as maximal independent set, maximal matching, and hitting set. 1 Introduction and Related Work All known techniques for derandomizing parallel algorithms come with the drawback of increasing the work by a \operatorname{poly}(\log n) factor. For instance, for the well-studied problem of maximal independent set, which was the main target of classic works by Karp and Wigderson [ KW84 ] , Luby [ Lub85 , Lub88 ] , and Alon, Babai, and Itai [ ABI86 ] , the currently best known deterministic parallel algorithms require at least m\operatorname{poly}(\log n) work. Hence, unless we have at least \operatorname{poly}(\log n) processors, these parallel algorithms are embarrassingly slower than their trivial sequential counterparts. This paper is centered on addressing this limitation. We present a novel, generic parallel derandomization technique via gradually rounding fractional solutions. We show its power by using it to obtain deterministic parallel algorithms—for maximal independent set, maximal matching, and hitting set—with work m\operatorname{poly}(\log\log n) , thus moving exponentially closer to true work efficiency. We next review the relevant context and state of the art, and then state our results. 1.1 Context Parallel Model—Work, Depth, and Work-Efficiency We follow the standard work-depth model [ JáJ92 , Ble96 ] , where the algorithm runs on p processors with write and read access to a shared memory. In the case of multiple concurrent writes to a memory location, we assume that an arbitrary one takes place. In any algorithm \mathcal{A} , its depth D(\mathcal{A}) is the longest chain of computational steps in \mathcal{A} , each of which depends on the previous ones. In other words, this is the time that it would take the algorithm to run even if we were given an infinite number of processors. The work W(\mathcal{A}) is the total number of computational steps in \mathcal{A} . The time T_{p}(\mathcal{A}) to run the algorithm on p processors clearly satisfies T_{p}(\mathcal{A})\geq\max\{D(\mathcal{A}),W(\mathcal{A})/p\} . By Brent’s principle [ Bre74 ] , we also know that T_{p}(\mathcal{A})\leq D(\mathcal{A})+W(\mathcal{A})/p . The objective in parallel computations is to devise algorithms that run faster than their sequential counterparts, and ideally, we want a speed-up proportional to the number of processors p . In particular, this requires the parallel algorithm to have a work bound equal/close to the best known sequential algorithm. Algorithms whose work bound matches the sequential counterpart are called work-efficient . A relaxation is nearly work-efficient algorithms, whose work bound can be a \operatorname{poly}(\log n) factor larger. These algorithms need at least \operatorname{poly}(\log n) processors to match (or beat) the speed of single-processor computation. We comment that much of the early work in the theory of parallel computation, in the early 1980s and before, prioritized the depth and allowed large polynomial work bounds. These results assumed a large polynomial number of processors. This was in line with the general state of algorithmic research at the time, focusing on polynomial time computation with less emphasis on the exact polynomial. However, starting in the late 1980s and certainly by the 1990s [ JáJ92 ] , the focus moved more and more on the work bound. The aim is to attain parallel algorithms that yield speed up—compared to sequential algorithms—for a relatively small number of processors (certainly much below linear, but ideally even close to constants). Indeed, this is the primary focus in recent research, and over the past decade, there have been numerous exciting results on achieving work-efficient or nearly work-efficient parallel algorithms for various problems. See, e.g., [ Fin18 , JLS19 , BGSS20 , Li20 , ASZ20 , CFR20 , DBS21 , AB21 , RGH+22 , REGH22 , GGR23 , GG24b ] . State of the Art in Parallel Derandomization We focus here on the maximal independent set (MIS) problem, which was the target of early work on parallel derandomization, and remains a central problem in the area. Karp and Wigderson [ KW84 ] gave the first (deterministic) parallel algorithm for MIS, and along the way commented that a simpler part of it provides a randomized algorithm. Their deterministic algorithm has \tilde{O}(n^{3}) work and \operatorname{poly}(\log n) depth. At the core of their algorithm is a parallel derandomization of the following nature: Their argument shows that there exists an independent set with a certain high score, by doing an averaging over all t -subsets of a (large) set of vertices. Hence, a randomly selected t -subset would also achieve a similarly high score (in expectation, or after a few repetitions). To make this deterministic, they show that the space of all t -subsets, which can have n^{\Theta(t)} options, can be replaced with a much more compact space of certain combinatorial designs, with only \tilde{O}(n) options, while retaining the averaging argument. Hence, one can check all of these options in parallel and obtain a deterministic algorithm. Luby [ Lub85 ] made the above derandomization much more generic, casting it as a derandomization for randomized algorithms with pairwise independence. He gave an elegant randomized parallel MIS algorithm with expected O(m) work and \operatorname{poly}(\log n) depth, and he showed that the analysis (of each round) can be done using merely pairwise independence. Hence, instead of the naive exponential-size space of n independent random variables, the space of randomness can be limited to O(n^{2}) points which are pairwise independent. One can check all of these in parallel and deterministically, and that results in a deterministic parallel MIS algorithm with O(m\cdot n^{2}) work. Alon, Luby, and Babai [ ABI86 ] independently presented similar algorithms for MIS, along with the same derandomization technique for pairwise-independent randomized algorithms with work overhead \Omega(n^{2}) , and its generalization to d -wise for constant d which has work overhead n^{\Theta({d})} . In a subsequent paper, Luby [ Lub88 ] noted that the main drawback of the above techniques is the blow up in the work bound. He explicitly phrased it in terms of the number of processors needed. To mitigate this issue, Luby gave an elegant parallel derandomization technique by doing a high-dimensional binary search:

Read the complete text