CS Paper Radar

Catalytic space-efficient algorithms for Distance and Determinant

Srijan Chakraborty, Samir Datta, Kushagra Shandilya

cs.CC cs.DS ·submitted 2026-10-30 13:33 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Unconditional Separation between LL and CLL

cs.CC ·2026-10-11 ·Shubham Bhardwaj
publishedtheory similarity 0.70
Abstract · 11 pages. v2: fixed an error in the upper bound concerning the endmarkers of the catalytic tape; thanks to András Salamon for pointing it ou…

Catalytic computation involves the study of Turing machines that are provided an additional catalytic tape (with arbitrary content) that the machine may use while ensuring that the tape contents are restored at the end of the computation. Although it is known that catalytic log-space machines are at least as powerful as non-deterministic log-space (and more), we do not have unconditional asymptotic separations. In this work, we prove an unconditional separation between a deterministic space complexity class and its catalytic counterpart. More precisely, at the doubly logarithmic scale, we show that catalytic Turing machines can provably compute more languages than standard deterministic doubly-logarithmic space machines. The separation is witnessed by the unary language $\mathrm{POW2} = \{1^n : n \text{ is a power of two}\}$. We construct a catalytic Turing machine that uses $O(\log \log n)$ bits of space and $O(\log n)$ bits of catalytic tape to decide $\mathrm{POW2}$, whereas any standard deterministic Turing machine requires $Ω(\log n)$ space to decide it.

0.30

Computing faster with a full memory: Catalytic algorithms break time-space lower bounds

cs.DS cs.CC ·2026-10-17 ·Adelmo Morrison Orozco, Nathan Sheffield, Ryan Williams
similarity 0.70
Abstract

We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation. In a natural output model, with $O(\log(n))$ free space and poly($n$) catalytic space, we give algorithms for sorting and the discrete Fourier transform running in time $n^{1+o(1)}$, and an algorithm for matrix multiplication running in time $n^{ω+ o(1)}$. In the same output model, without additional catalytic space, sorting and DFT are known to require time-space product $Ω(n^2)$, and matrix multiplication is known to require time-space product $Ω(n^3)$ [Borodin and Cook, 1982] [Beame, 1991] [Yesha, 1984] [Abrahamson, 1991]. This is the first unconditional demonstration that (uniform, non-relativized) catalytic logspace algorithms can outperform their (non-catalytic) logspace counterparts. We give several further results relevant to fast catalytic algorithm design. We observe that many applications of sorting, FFT, and fast matrix multiplication (e.g., kSUM, integer multiplication, and clique counting) can be performed catalytically, giving catalytic logspace algorithms matching (up to subpolynomial factors) the best known unbounded-space runtimes. Furthermore, we give a fast and simple catalytic algorithm for evaluating low-depth threshold circuits, improving the previously known runtime bound from $\widetilde O(|C|4^df)$ to $\widetilde O(|C|2^d)$, where $|C|$ is the total size (i.e. number of wires) of the circuit, $d$ is the depth, and $f$ is the maximum fan-in.

0.28

Graph Spectral Sparsification is in Catalytic Logspace

cs.DS cs.CC ·2026-08-21 ·Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld
similarity 0.67
Abstract · 29 pages

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.

0.20

Space Complexity of Reachability in Simple Path Graphs

cs.CC ·2026-10-20 ·Krishnamoorthy Dinesh, Chandana Sasidharan
published similarity 0.63
Abstract · 17 pages, 9 figures

One of the central questions in space complexity is whether nondeterministic logspace computations ($\textsf{NL}$) can be simulated in unambiguous logspace ($\textsf{UL}$). A stronger notion, \emph{reach unambiguity} ($\textsf{RUL} \subseteq \textsf{UL} \cap \textsf{co}\textsf{UL}$), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph reachability is $\textsf{NL}$-complete, planar graph reachability is in $\textsf{UL}$ and undirected graph reachability is in deterministic logspace ($\textsf{L}$). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. - For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), Lange (Lange 97) showed that reachability is in $\textsf{RUL}$. As our main result, we show that for simple path graphs (introduced in Kannan et.al. 08), which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, we show that the reachability problem lies in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. - Our first result can also be equivalently stated as: the recognition problem for simple path is in $\textsf{UL} \cap \textsf{co}\textsf{UL}$ if and only if the reachability problem restricted to simple path graphs is also in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for graph classes. Observe that for any graph class, solving reachability (for the class) also solves the recognition problem for that class. We show that for reach unambiguous graphs, solving recognition is as hard as solving reachability (making both of them $\textsf{RUL}$-complete). (Abstract shortened to meet arXiv limits)

0.63

Metric Planarity Testing is Hard

cs.DS ·2026-10-11 ·Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak, Hung Le, Bartłomiej Lewandowski +1 more
theory similarity 0.61
Abstract · 9 figures, 27 pages

A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for either a polynomial-time algorithm or an NP-hardness proof for metric planarity testing: given a metric space $(X,d_X)$, determine whether there exists an edge-weighted planar graph $G=(V,E,w)$ with $X\subseteq V$ that realizes the distances in $X$, meaning that $d_G(x,y)=d_X(x,y)$ for every $x,y\in X$. This question arose in the context of research on metric embeddings and their applications in computer science since the mid-1990s. Over the past few decades, polynomial-time algorithms have been developed for several special cases. In this work, we show that metric planarity testing is NP-hard, in sharp contrast to graph planarity testing. Our reduction yields a stronger result: under the Exponential Time Hypothesis (ETH), no $2^{o(n)}$-time algorithm for metric planarity testing exists, where $n$ is the number of points in the metric. To complement our ETH lower bound, we give two algorithmic results: (i) an algorithm for computing a metric planar embedding in $2^{\tilde{O}(n^2)}$ time and (ii) a $(1+ε)$-approximation algorithm in $2^{\tilde{O}(n)}$ time for any fixed $ε\in(0,1)$. The second algorithm produces a planar graph that preserves the input metric up to a factor of $(1+ε)$.

0.29

An Operator Approach to Register Programs for Catalytic Computing

cs.CC ·2026-09-16 ·Antoine Vinciguerra
theory similarity 0.61
Abstract

In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of problems solvable in space $s$ with an additional catalytic tape of size $c$, a tape whose initial content must be restored at the end of the computation. A central ingredient of their proof is the register program model. Namely, they constructed a uniform family of register programs that computes $x^n$ using $n$ registers and four accesses to $x$. Since then, determining the number of registers and input accesses required to compute a polynomial of a given degree has become a central question in the study of catalytic computation. On one hand, we prove that the four-access bound of Buhrman et al.\ is optimal: every passive-output register program computing a polynomial of degree greater than three requires at least four input accesses, independently of the number of registers. On the other hand, we show that their register bound is not optimal. For every $t\geq2$ and every field $K$ of characteristic $0$ or greater than $2t-1$, we construct a register program for $x^{2t-1}$ with four input accesses and $t$ registers. Our proofs rely on derivations and their exponential operators. This approach represents a register program as a series of exponential derivation operators, reducing register restoration to an operator identity. Finally, we use the uniform family of register programs to improve known trade-offs for catalytic streaming algorithms and register programs for matrix powering. The generalization of the lower-bound methods and the construction of the uniform family of register programs were developed with assistance from ChatGPT 5.6.

0.15

Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

cs.DS cs.CCcs.DMmath.CO ·2026-08-25 ·Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk
similarity 0.60
Abstract · 31 pages, 5 figures

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

0.37

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.60
Abstract

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

0.35