CS Paper Radar

True Work-Efficiency in Parallel Derandomization

Mohsen Ghaffari, Cheng Jiang

cs.DS ·submitted 2026-08-22 14:41 UTC · v1

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 $(Δ+1)$-coloring, where $Δ$ denotes the maximum degree of the graph, the best-known deterministic parallel algorithms with polylogarithmic depth used $Ω((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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Fast Deterministic Algorithm for $(Δ+1)$-edge coloring in CONGEST

cs.DC ·2026-08-19 ·Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
theory similarity 0.70
Abstract

Vizing's theorem states that any graph of maximum degree $Δ$ can be properly edge-colored with $Δ+ 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(Δ+ 1)$-edge coloring can be found deterministically in $poly(Δ,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(Δ,\log n)$-round algorithm for $(Δ+ 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.

0.16

More Efficient Parallel $(Δ+1)$-Edge Coloring

cs.DS ·2026-09-28 ·Jeremy T. Fineman, Seyed Ali Mohammadi
similarity 0.68
Abstract

This paper gives two parallel algorithms for $Δ+1$ edge coloring, where $Δ$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}(Δ^3)$ span and $\tilde{O}(m Δ^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}(Δ^2)$ span and $\tilde{O}(m Δ^2 )$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}(Δ^4)$ span and $\tilde{O}(m Δ^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(Δ)$ improvement on span and $\tilde{O}(Δ^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}(Δ^2)$ and $\tilde{O}(Δ^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.

0.06

Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs

cs.DS ·2026-08-17 ·Trevor Vaughn
similarity 0.64
Abstract

The Minimum $k$-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least $k$ connected components. We consider only $k\ge3$. The fastest previous algorithm for weighted graphs ran in $n^{k-2}(m+n)(\log n)^{O(k^2)}$ randomized time~\cite{LV26}; on dense graphs this is $\widetilde O_k(n^k)$, and for $k=3$ it gives an $\widetilde O(nm)$-time algorithm. We improve the dense-graph exponent from $k$ to $k-1$ and obtain the same exponent deterministically. After aggregating parallel edges in $O(m)$ time, our randomized algorithm runs with high probability in \begin{equation*} k^{O(k^2)}n^{k-1}\log^2n \end{equation*} time, while our deterministic algorithm runs in \begin{equation*} k^{O(k^2)}n^{k-1}\log^{O(1)}n \end{equation*} time. In particular, weighted Minimum $3$-Cut can be solved in $O(n^2\log^2 n)$ randomized time and in $\widetilde O(n^2)$ deterministic time. The algorithms have two main components. First, we give a faster algorithm for weighted Minimum $3$-Cut. After handling optima with a very small side and optima with two light sides, the remaining optimum has a unique structured side. Tree packing reduces its completion to a batched collection of $2$-respecting cut problems. Second, we reduce Minimum $k$-Cut to Minimum $3$-Cut by enumerating a bounded family of light-cut candidates and recursively completing either side of each candidate. If the enumeration produces too many cuts, then we can instead produce an optimum $k$-cut directly. We derandomize the $3$-cut algorithm using a deterministic near-minimum-cut skeleton, and derandomize the reduction using a specialized $4$-cut algorithm using the skeleton, the constructive light-cut bounds, and the deterministic spectral sparsifier of \cite{BSS12}.

0.23

Streaming Hypergraph Coloring via Palette Sparsification

cs.DM math.COcs.DS ·2026-08-20 ·Artur Czumaj, Pan Peng, Ruizhe Shi, Christian Sohler
theory similarity 0.63
Abstract · 25 pages. This revision merges the original manuscript with independent work by Czumaj, Peng, and Sohler

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $Δ$ with $O(Δ^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $Θ(\sqrt{\log n})$ colors from a palette of size $O(Δ^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of $Δ$ for which any deterministic one-pass algorithm requires $\exp(Δ^{Ω(1)})$ colors.

0.37

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

cs.DS ·2026-10-16 ·Eliyahu Yablon
similarity 0.63
Abstract

The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized $O\left(m^{1+2/(k-1)} n^{1/(k-1)}\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors $k = c\frac{\log n}{\log \log n}$ where $c>5$, our algorithm gives a runtime of $O\left(m (\log n)^{5/c}\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\frac{\log n}{\log \log n}$ yields a running time of $O\left( \frac{cn (\log n)^{2 + 4/(3c)} }{\log \log n} + m\log n\right)$ (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call ``random filtering.'' That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.

0.18

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL

cs.DS ·2026-11-04 ·Mohsen Ghaffari, Sijin Peng
similarity 0.63
Abstract

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

0.20

Constant-Factor Matching-Size Estimation in Random-Order Streams

cs.DS ·2026-11-16 ·Alireza Farhadi, Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.63
Abstract

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

0.12

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.62
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21