This paper achieves truly work-efficient parallel derandomization by obtaining linear work bounds of $O(m+n)$, thereby achieving truly work-efficient parallel derandomization.
Abstract
A longstanding limitation of known techniques for parallel derandomization was that they incurred at least polylogarithmic overhead in work. For instance, for fundamental and frequently used problems such as maximal independent set, maximal matching, and $(\Delta+1)$-coloring, where $\Delta$ denotes the maximum degree of the graph, the best-known deterministic parallel algorithms with polylogarithmic depth used $\Omega((m+n)\mathrm{poly}(\log n))$ work on $n$-vertex, $m$-edge graphs; see, e.g., Luby [FOCS'88]. Consequently, at least $\mathrm{poly}(\log n)$ processors were needed for these algorithms to outperform straightforward single-processor algorithms. Recently, Ghaffari and Grunau [FOCS'25] introduced a new parallel derandomization method that substantially reduced the overhead from $\mathrm{poly}(\log n)$ to $\mathrm{poly}(\log\log n)$, achieving work bounds of $O((m+n)\mathrm{poly}(\log\log n))$. In this paper, we settle this line of research by obtaining linear work bounds of $O(m+n)$, thereby achieving truly work-efficient parallel derandomization.
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and V\'egh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].
For every $\varepsilon>0$, it is NP-hard to $n^{1-\varepsilon}$-approximate Max Independent Set in $n$-vertex graphs [Hastad'96, Zuckerman'07]. In triangle-free graphs, a simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\varepsilon>0$, an $n^{1/4-\varepsilon}$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomass\'e, Tran, Watrigant; ESA'20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\varepsilon}$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal F$ of graphs, each containing at least one cycle, for any $\varepsilon>0$, an $n^{\mu(\mathcal F)-\varepsilon}$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal F$ as a subgraph implies that NP $\subseteq$ BPP, where $\mu(\mathcal F) := 1 - \max\limits_{H \in \mathcal F}~\min\limits_{U \subseteq V(H), H[U] \text{contains a cycle}} (|U|-2)/(|E(H[U])|-1)$.
This work generalizes and combines tools from the $(k+2)-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023] and yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.
The main result shows that the exact average-case complexity of this fundamental problem is $\Theta(nk)$ for every $k \leq n^{c'}$ and some $c'\in (0, 1)$, and reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input.
Cassandra Marcussen, Edward Pyne, R. Rubinfeld et al.· 0 citations
We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs $G=(V,E)$ using only a few shared random bits. Specifically, in the $\congest$ model, we compute a matching whose expected number of blocking pairs is at most $\varepsilon |E|$ in $O\left(\frac{\log(1/\varepsilon)}{\varepsilon^4}\right)$ rounds using $O\left(\log(1/\varepsilon)\right)$ shared random bits. Thus, for every constant $\varepsilon>0$, the round complexity is $O(1)$, independent of the number of vertices and the maximum degree. Previous algorithms achieve constant round complexity only for bounded-degree or almost-regular graphs; on general graphs, their round complexity depends polylogarithmically on $n$. Our main technical idea is a degree-guarded freezing rule that allows widely varying degrees to be handled by a single global charging argument, avoiding the $\Theta(\log n)$ successive degree thresholds used in previous work. The shared random bits are used only to select a common random output iteration. As consequences, we obtain an $O\left( \frac{\log(1/\varepsilon)}{\varepsilon^4} + \frac{\log n}{\varepsilon} \right)$-round $\congest$ algorithm without pre-shared randomness, via a low-diameter decomposition, and an $O\left(\frac{\log(1/\varepsilon)}{\varepsilon^4}\right)$-round algorithm in the fully-scalable Massively Parallel Computation ($\mpc$) model with linear total memory.