CS Paper Radar

Graph Spectral Sparsification is in Catalytic Logspace

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld

cs.DS cs.CC ·submitted 2026-08-21 19:56 UTC · v1

Abstract

We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph $G$ on $n$ vertices and $\varepsilon>0$, our algorithm outputs an $\varepsilon$-spectral sparsifier of $G$ with $O(n\varepsilon^{-2}\log n)$ edges, matching the effective resistance sampling of Spielman and Srivastava (STOC 2008). This gives a new, natural problem in catalytic logspace that is not known to be in deterministic $\mathbf{NC}$ or $\mathbf{SC}$. Our main contribution is an entirely new technique in the compress--or--random paradigm for catalytic logspace that we believe will have further applications. We first analyze effective-resistance sparsification using a pessimistic estimator that can itself be computed in catalytic logspace. The estimator is motivated by the viewpoint of graph quasirandomness and immediately gives a simple, deterministic greedy algorithm for graph sparsification. Subsequently, we show that such a pessimistic estimator can be transformed into an algorithm that performs an in-place compression of a string with bad potential. Our algorithm is based on using the potential function to define a measure over strings, and implementing arithmetic coding using this measure in-place. This compression technique is substantially distinct from all prior tools in the field of catalytic computation.

Comment
29 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs

cs.DS ·2026-08-14 ·Jason Li, Trevor Vaughn
similarity 0.68
Abstract

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$-vertex, $m$-edge multigraph, let $0<\varepsilon\le1/2$. Assuming $m,\varepsilon^{-1}\le n^{O(1)}$ and the ratio of maximum to minimum weight is polynomially bounded, we deterministically construct a $(1\pm\varepsilon)$-spectral sparsifier with \[ O\!\left(n\varepsilon^{-2}\log^{24+o(1)}n\right) \] edges in \[ m^{1+o(1)}+O\!\left(n^2\varepsilon^{-9/2}\log^{113/2+o(1)}n\right) \] time. The construction has two main ingredients. First, we sparsify an approximately regular expander by partitioning its edges into few matchings and viewing their normalized Laplacians as an isotropic family of positive semidefinite matrices. Rather than sample from this family and apply matrix Chernoff, we select matchings deterministically using a pessimistic estimator. We evaluate the resulting conditional-expectation scores in two ways to produce two algorithms: using dense matrix multiplication and sparsely using polynomial approximations to the inverse square root and matrix exponential. Deterministic expander decomposition, along with replacing vertices by fixed expander graphs to achieve approximate regularity, extends these algorithms to general graphs. Second, a recursive blocking scheme applies the dense algorithm to smaller subgraphs and the sparse algorithm to their union, balancing their costs. Reusing the resulting algorithm as the dense algorithm gives $α_{r+1}=3-1/(α_r-1)$, starting from $α_0=ω$. After $O(\log n)$ levels, the exponent is $2+O(1/\log n)$, yielding $m^{1+o(1)}+\widetilde O_{\varepsilon}(n^2)$ time.

0.04

Catalytic space-efficient algorithms for Distance and Determinant

cs.CC cs.DS ·2026-10-30 ·Srijan Chakraborty, Samir Datta, Kushagra Shandilya
theory similarity 0.67
Abstract

Catalytic computation reuses potentially large but in-use space (or catalytic space) which must be restored to its initial contents while the clean space is small. This allows all problems in $\mathsf{NL}$ and even larger classes to be in catalytic logspace [Buhrman et al, STOC2014]. In [Chmel et al, CCC2026] the catalytic space for reachability was restricted to sublinear space (specifically, $n \big/ 2^{θ(\sqrt{\log n})}$ space) while remaining in polynomial time. This matches the non-catalytic bounds from [Barnes et al, SICOMP1998]. We extend the reachability bound to shortest distance, proving a simultaneous sublinear catalytic space and polynomial time bound (henceforth called, sublinear $\mathsf{CLP}$). This is the first simultaneous sublinear space and polynomial time bound for distance even without the catalytic discipline. Moreover, our bound works even for polynomially weighted graphs. Along the way we prove simultaneous near linear catalytic space ($\mathcal{O}(n\log^{O(1)}{n})$) and polynomial time bounds for the determinant. We also show some applications to planar matching problems. Our starting point was catalytic computation of reachability in directed graphs by [Cook-Pyne, ITCS2026]. [Edenhofer, arXiv:2602.21088] used it to give a tradeoff between catalytic and non-catalytic space, while [Chmel et al, CCC2026] compress the graph to a smaller graph preserving $s,t$-reachability to achieve a smaller space bound. All three can be modified to yield an algorithm for unweighted distance. Our contribution is to define an approximation to the walk polynomial in weighted graphs that allows us to infer weighted $s,t$-distance in sublinear $\mathsf{CLP}$. We do so by non-trivially combining elements from each of the above three papers.

0.17

Directed Singular-Value Sparsifiers with $O(n \log n/ε^2)$ Arcs

cs.DS cs.DM ·2026-11-10 ·Emile Anand
theory similarity 0.64
Abstract · 44 pages

Given an unweighted directed graph, a sparsifier is a nonnegative reweighting of original arcs that preserves every in-degree and out-degree exactly. In this work, we study singular-value sparsifiers, which are generalizations of spectral sparsifiers. Singular-value sparsifiers find a number of applications in theoretical computer science, such as maintaining directed cuts and flows, speeding up directed Laplacian solvers, and sparsifying dense weight matrices in neural networks. Strong singular-value (SV) approximation supports sparse representations of directed random walks with guarantees that remain stable under products, and controls bilinear error in the left and right Schur-complement metrics. We prove that every unweighted directed graph on $n$ vertices admits an $\varepsilon$-SV sparsifier with $O(n\log(2n)/\varepsilon^2)$ arcs, improving the $O(n\log^5 n/\varepsilon^2)$ support bound of Lau, Wang, and Zhou. The sparsifier is a nonnegative reweighting of original arcs and preserves every in-degree and out-degree exactly. We also give a randomized construction with $\tilde{O}(m+n)$ real-arithmetic running time, where $m$ is the input support size, and the output has the same support bound and rational weights of polynomial bit length.

0.17

Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses

cs.DS math.PR ·2026-09-13 ·Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao
theory similarity 0.63
Abstract · 79 pages

Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We determine how finite graph structure controls their sharp spectral growth. For every fixed simple graph shape in the dense Rademacher model, including overlapping or empty matrix boundaries, we prove $\mathbb E\|M_α\|=Θ_α(n^{(v+h-s)/2}(\log n)^{a_*/2})$, where $v$ counts vertices, $h$ isolated summation vertices, $s$ the minimum boundary-separator size, and $a_*$ maximizes an active-component count over minimum separators. Thus two finite cut optimizations determine both the polynomial and logarithmic exponents. The formula closes the polylogarithmic gap in separator bounds, and an infinite family with identical coarse parameters but different norms shows that the logarithmic exponent records genuinely new structure. The proof controls all defect layers in growing trace moments by converting label loss into separator excess; conditional flattening and synchronized fluctuations yield matching lower bounds. We extend the analysis to specified independent-factor chaoses, local weights, unequal dimensions, bounded asymmetric noise, Gaussian inputs, and fixed-degree Hermite inputs. Applications include degree-four clique SoS feasibility for $9\le k\le c\sqrt n$ without an asymptotic logarithmic loss, and Gaussian random tensor networks: deviation thresholds, sharp expected scales, entropy estimates, and, for connected loopless equal-dimensional networks, convergence of the rescaled largest output eigenvalue to the exact right edge of the limiting law. These results connect finite structure to sharp growth scales, and additional algebraic and spectral structure to full feasibility and exact limiting constants.

0.32

Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

cs.DS ·2026-11-02 ·Honghao Lin, Vahab Mirrokni, David P. Woodruff
similarity 0.63
Abstract

A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using $\tilde{O}(n/\varepsilon^3)$ bits of space. We improve the space to $\tilde{O}(n/\varepsilon^2)$ bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in $\tilde{O}(1)$ time, and recovers, in $\tilde{O}(n/\varepsilon^2)$ time, a reweighted subgraph with $O(n\varepsilon^{-2}\log^2 n)$ edges that preserves every cut within a factor of $1\pm\varepsilon$. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.

0.24

A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability

cs.DS ·2026-10-30 ·Zhijie Zheng
similarity 0.62
Abstract · 19 pages

We give a fully polynomial randomized approximation scheme for all-terminal unreliability in explicitly represented undirected hypergraphs of arbitrary rank. The algorithm estimates the probability that independent hyperedge failures disconnect the hypergraph, allowing a different rational failure probability for every edge. For a common failure probability, this improves the quasi-polynomial approximation schemes of Cen, Li, and Panigrahi to polynomial time and answers the polynomial-time approximation question reiterated in their subsequent work on graphs. The construction turns their representative-survival bound into an importance sampler whose relative second moment is bounded solely in terms of the number of vertices. We protect one randomly chosen representative pair during contraction, correct the path likelihood, and divide by the number of pairs surviving at the end. The resulting unbiased estimator has relative second moment at most $\binom n2$, even when unreliability is exponentially small. A minimum-cut normalization makes this estimator implementable with polynomially bounded precision: the residual likelihood becomes a survival probability in an auxiliary absorbing process, which admits rational discretization with a fixed random-bit budget. Logarithmic rate rounding and an exact weighted minimum cut extend the construction to unequal rational failure probabilities. The algorithm's worst-case running time and random-bit usage are polynomial in the input length, the inverse relative error, and $\log(1/δ)$ for confidence $1-δ$.

0.18

A Linear-Time Approximation Scheme for the Densest Subgraph Problem

cs.DS ·2026-08-11 ·Elena Grigorescu, Mehrshad Taziki
similarity 0.61
Abstract

In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.

0.04

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$-Uniform Directed Graphs

cs.DS ·2026-10-13 ·Richard Peng, Sushant Sachdeva, Junzhao Yang, Yibin Zhao
similarity 0.61
Abstract

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $γ$, we give a $(1\pm\varepsilon)$ effective-resistance data structure with expected update time $O(γ^{-4}\varepsilon^{-2}\log n\log^4(n/\varepsilon))$ and expected $O(1)$ query time. For directed graphs, somewhat surprisingly, the OMv conjecture precludes a fast data structure based on rapid mixing conditions alone. To address this, we introduce the notion of $κ$-uniform directed graphs, which requires the stationary distribution to $κ$-approximate the uniform distribution, and show that in this setting, random walk based data structures with $\text{poly}(κ, \log{n}, \varepsilon^{-1})$ update/query times are possible.

0.21