Efficient Catalytic Graph Algorithms

Cook, James; Pyne, Edward

doi:10.4230/LIPIcs.ITCS.2026.43

Efficient Catalytic Graph Algorithms

James Cook

Toronto, Canada Edward Pyne

MIT, Cambridge, MA, USA

Abstract

We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems.

First, a randomized catalytic algorithm for $s\to t$ connectivity running in $\widetilde{O}(nm)$ time, and a deterministic catalytic algorithm for the same running in $\widetilde{O}(n^{3}m)$ time. The former algorithm is the first algorithmic use of randomization in $\mathsf{CL}$ . The algorithm uses one register per vertex and repeatedly “pushes” values along the edges in the graph.

Second, a deterministic catalytic algorithm for simulating random walks which in $\widetilde{O}(mT^{2}/\varepsilon)$ time estimates the probability a $T$ -step random walk ends at a given vertex within $\varepsilon$ additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges.

Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in $n$ .

Keywords and phrases:

catalytic computing, graph algorithms, catalytic logspace

Funding:

Edward Pyne: Supported by NSF award CCF-2310818.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Graph algorithms analysis ; Theory of computation

\rightarrow

Pseudorandomness and derandomization ; Theory of computation

\rightarrow

Complexity classes

Related Version:

Full Version: https://arxiv.org/abs/2509.06209

Acknowledgements:

E.P. thanks Ryan Williams for encouragement to think about algorithms in CL and useful discussions, and Ian Mertz for the suggestion to work over different moduli. J.C. thanks Michal Koucký and the CCC reviewers for useful suggestions.

DOI:

10.4230/LIPIcs.ITCS.2026.43

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

1.1 Catalytic space

In the catalytic space model, an algorithm has two tapes to use as memory: a smaller ordinary tape, and a larger “catalytic” tape which starts out filled with arbitrary data. The algorithm may freely write to and read from both tapes, but when it finishes, the catalytic tape’s original content must be restored. Often the working tape has size $O(\log n)$ and the catalytic tape has size $\operatorname{poly}(n)$ , defining the decision class catalytic logspace or $\mathsf{CL}$ . Buhrman, Cleve, Koucký, Loff and Speelman [2] initiated the study of this model with their surprising result that evaluation of logarithmic depth threshold circuits was possible in $\mathsf{CL}$ , from which it follows for example that $s\rightarrow t$ connectivity and estimation of random walks (the complete problems for nondeterministic logspace ( $\operatorname{\mathsf{NL}}$ ) and randomized logspace ( $\mathsf{BPL}$ ) respectively) are in $\mathsf{CL}$ .

Broadly speaking, two ways to take advantage of catalytic space have been explored previously: compression-based techniques are able to make use of incompressible catalytic tapes (as randomness, for example); and algebra-based techniques treat the tape as an array of registers which they use to execute a “straight-line program”, a pre-determined sequence of mathematical operations. The original $\operatorname{\mathsf{TC}}^{1}\subseteq\mathsf{CL}$ result is an example of the algebraic approach. The compression-based approach began with a “compress-or-random” argument that $\mathsf{BPL}\subseteq\mathsf{CL}$ (Mertz [8] gives a sketch of it). Several subsequent works [6, 10, 5, 7] applied this technique further, with Cook, Li, Mertz and Pyne [5] using it to derandomize randomized $\mathsf{CL}$ itself. All of these results in both branches have a “complexity” flavor – in particular, the runtime for the relevant problem is some large polynomial.¹¹1Cook [4] implemented a register program for $s\rightarrow t$ connectivity with an estimated runtime of $\Theta(n^{8})$ , and catalytic tape size $\Theta(n^{3}\log n)$ .

We give new techniques for deciding graph connectivity and estimating random walks. Our algorithms are very simple and implementable, and allow a precise analysis of the catalytic space consumption and runtime.²²2For the runtime bounds, we assume we have RAM access to the catalytic tape and oracle access to the graph. This does not affect the structure of the class (as we can simulate a catalytic RAM with a standard catalytic machine with a polynomial slowdown). We hope this will initiate the study of $\mathsf{CL}$ from an algorithmic perspective.

1.2 Our Results: Connectivity

We first state our results for connectivity, beginning with our deterministic algorithm:

Theorem 1.

There is a catalytic algorithm that, given a simple directed graph with $n$ vertices and $m$ edges together with vertices $s, t$ , decides whether there exists a path from $s$ to $t$ . The algorithm uses $O(\log n)$ workspace and $\widetilde{O}(n^{2})$ catalytic space, and runs in time $\widetilde{O}(n^{3}m)$ .

Next, we give a randomized algorithm that improves the runtime to $\widetilde{O}(nm)$ and space usage to $\widetilde{O}(n)$ , only a factor of $n$ in runtime from the linear-workspace BFS algorithm:

Theorem 2.

There is a randomized catalytic algorithm that, given a simple directed graph with $n$ vertices and $m\geq n$ edges together with vertices $s, t$ , decides whether there exists a path from $s$ to $t$ . The algorithm uses $O(\log n)$ workspace and $\widetilde{O}(n)$ catalytic space, and runs in time $\widetilde{O}(nm)$ .

We remark that a randomized (one-sided error) catalytic algorithm always resets the catalytic tape no matter the random coins. If there is no $s\rightarrow t$ path, the algorithm always returns no, and if there is an $s\rightarrow t$ path returns yes with probability at least $1/2$ .

As far as we know, this result is the first use for randomness in catalytic computing – rather than using it to place a new problem in the class (now provably impossible [5]), we use it to give an algorithmic speedup.

$\blacktriangleright$ Remark 3.

The best known algorithms for stconn either use space $O(\log^{2}n)$ and superpolynomial time [11], or polynomial time and slightly sublinear space $n/2^{\sqrt{\log n}}$ [1]. Under the assumption there does not exist a randomized stconn algorithm that simultaneously uses $n^{1-\varepsilon}$ space and polynomial time, the catalytic space usage of Theorem 2 is optimal up to subpolynomial factors.³³3A randomized catalytic logspace algorithm for $s\rightarrow t$ connectivity using $n^{1-\varepsilon}$ catalytic space would imply a randomized $n^{1-\varepsilon}$ space, polynomial-time algorithm for $s\rightarrow t$ connectivity [2]. We view matching the total space of [1] with a catalytic algorithm to be an interesting open question.

In fact, we can obtain an additional desirable property. The practical motivation for $\mathsf{CL}$ is to borrow temporarily unused space to perform useful computation. Unfortunately, if any part of the borrowed section of memory is needed during the computation of the catalytic machine, the original owner may need to wait for the entire catalytic computation to finish. As such, existing catalytic algorithms do not seem to permit sharing a single section of memory without huge latency.⁴⁴4Alongside the large runtime of prior algorithms, this was mentioned as the primary issue for practical catalytic computing by Cook [4]. To rectify this problem, we define a notion of catalytic algorithms that must permit fast query access to the original memory configuration at all times:

Definition 4.

A catalytic algorithm $A$ is locally revertible in time $t$ if at any point during the execution of $A$ with initial tape $\tau$ , the algorithm can be paused and queried on an index $i$ , and will return $\tau_{i}$ in time $t$ (and then continue its execution).

We show that (at the cost of polynomially more catalytic space) our randomized connectivity algorithm can be made locally revertible for $t=\operatorname{polylog}(n)$ :

Theorem 5.

There is a randomized catalytic algorithm that, given a simple directed graph with $n$ vertices and $m\geq n$ edges together with vertices $s, t$ , decides whether there exists a path from $s$ to $t$ . The algorithm uses $O(\log n)$ workspace and $\widetilde{O}(n^{3})$ catalytic space, and runs in time $\widetilde{O}(nm)$ . Moreover, the algorithm is locally revertible in time $\operatorname{polylog}(n)$ .

As far as we are aware, no previous catalytic algorithm is locally revertible for any time bound smaller than its runtime. This new property strengthens the motivation for catalytic space: rather than borrowing an unused hard drive, the catalytic algorithm only needs to borrow the ability to write to that hard drive, since at all times the original data will be accessible for reading with small latency.

1.3 Our Results: Random Walks

Next, we give an efficient catalytic simulation of random walks:

Theorem 6 (random walk on a general graph).

There is a catalytic algorithm that, given a graph with $n$ vertices and $m\geq n$ edges, together with vertices $s, t$ and parameters $T\in\mathbf{N},\varepsilon>0$ , returns $\rho$ such that

\left|\rho-\Pr[\text{$T$-step random walk from $s$ ends at $t$}]\right|\leq\varepsilon\ldotp

The algorithm runs in time $\widetilde{O}(mT^{2}/\varepsilon)$ and uses $O(\log(mT/\varepsilon))$ workspace and $\widetilde{O}(nT\cdot\log(m/\varepsilon))$ catalytic space.

Prior algorithms for random walks are primarily based on logspace derandomization techniques that are not practically efficient. For estimating sub-polynomial length walks to inverse sub-polynomial error, our algorithm runs in almost linear time $m^{1+o(1)}$ .

If $G$ is guaranteed to be acyclic, the algorithm can be made to use less time and space by skipping a transformation that removes cycles (see Theorem 21). Alternatively, naïvely applying the algorithm for acyclic graphs on a graph with cycles produces an interesting result: the algorithm is no longer catalytic, but produces a walk with visit counts matching a true random walk’s stationary distribution, after a number of steps which depends on the mixing time. For details, see Theorem 29.

1.4 Our Technique: Connectivity

We will give a catalytic algorithm that, given a graph $G=(V,E)$ on $n$ vertices, determines if there exists a path from $s$ to $t$ . We virtually lift $G$ to a layered graph on $(n+1)$ layers with vertex set $\{0,\ldots,n\}\times V$ , where we place an edge from $(i,u)$ to $(i+1,v)$ if $(u,v)\in E$ .

Next, for every $v\in V$ and timestep $i\in\{0,\ldots,n\}$ , allocate an $\ell=\widetilde{O}(n)$ bit register on the catalytic tape, which we denote $R_{(i,v)}$ , and interpret the register as a number in $\mathbf{Z}/2^{\ell}\mathbf{Z}$ . Let the initial value of the register be $\tau_{(i,v)}$ .

We define an edge push as, for an edge $((i,u),(i+1,v))$ in the lifted graph, setting

R_{(i+1,v)}\leftarrow R_{(i+1,v)}+R_{(i,u)}.

For each layer $i=0,\ldots,n-1$ in sequence, we perform an edge push for every edge in the layer.

Let $\alpha_{(n,t)}$ be the final value of $R_{(n,t)}$ after pushing along every edge. Note that we can easily revert the catalytic tape by performing a reverse edge push on every edge in every layer, where we subtract the register instead of adding. Now consider incrementing $R_{(0,s)}$ (i.e. the register of the start vertex in the first layer) by $1$ and performing the same sequence of edge pushes; let the new final value of $R_{(n,t)}$ be $\alpha^{\prime}_{(n,t)}$ . We show via an inductive argument that $\alpha_{(n,t)}^{\prime}-\alpha_{(n,t)}$ is exactly the number of length- $n$ paths from $s$ to $t$ , modulo $2^{\ell}$ (and by adding a self-loop to $t$ we can assume that if an $s\rightarrow t$ path exists, there exists an $s\rightarrow t$ path of length $n$ ). By repeatedly executing the edge push sequence and comparing $\alpha_{(n,t)}$ to $\alpha^{\prime}_{(n,t)}$ bit by bit, we determine whether their difference is nonzero – equivalently, whether there exists an $s\rightarrow t$ path.

Figure 1: Pushing values along edges to detect whether a

+1

is propagated from

s

to

t

.

Improving the runtime with randomness

Unfortunately, since the number of paths from $s$ to $t$ can be exponential in $n$ and we count the number of paths mod the register size, our deterministic algorithm must take the register size $\ell$ to be $\Omega(n)$ , so pushing a single edge takes linear time. Moreover, we must compute the entire sequence of pushes $\Omega(\ell/\log n)=\widetilde{\Omega}(n)$ times to compare $\alpha_{(n,t)}$ to $\alpha^{\prime}_{(n,t)}$ . To avoid this slowdown, we use randomness. Instead of working mod $2^{\ell}$ for $\ell=\Omega(n)$ , we pick a random small modulus $q$ and work mod $q$ . If the number of paths is nonzero, with reasonable probability we will have

\alpha_{(n,t)}-\alpha^{\prime}_{(n,t)}\not\equiv 0\pmod{q}

from which the algorithm can infer that there is a path from $s$ to $t$ . In this way, we reduce the size of each register to $O(\log n)$ bits.

If $q$ is not a power of two, not all strings of length $\ell$ will correspond to values mod $q$ , so we must ensure that each register is “valid” before running the algorithm. This problem was solved before by Buhrman et. al. [2, Lemma 15], but their approach is not fast enough for us. Instead, we use a larger modulus $d q$ chosen so that $2^{\ell}-dq$ is small, and then draw a random shift $\beta\in[2^{\ell}]$ (which we record on the worktape) and add $\beta$ to every register. With high probability over $\beta$ , this ensures every register contains a value less than $d q$ (and otherwise we abort).

Local revertibility

Next, we discuss how to achieve local revertibility. After performing all edge pushes onto a register $R_{a=(i+1,v)}$ , the current value of this register is exactly its original value $\tau_{a}$ plus

\sum_{u:(u,v)\in E}R_{(i-1,u)}

where $R_{(i-1,u)}$ is the current value of the register in the previous layer. Thus, if we receive a query for the initial value $\tau_{a}$ of this register, we can iterate over the in-neighbors of $v$ , subtract off the register values of the previous layer, and thus return $\tau_{a}$ . The time for this operation is essentially the product of the in-degree of $v$ and register size. Since we have already reduced the register size to $O(\log n)$ , it suffices to ensure our graph has bounded in-degree, which we show we can do with a standard transformation (Lemma 12).

Decreasing the number of registers

Finally, as written we use $n^{2}$ registers, one per vertex and timestep. In fact, we can simply use two sets of registers, one for odd and one for even timesteps, and alternate. This saves a factor of $n$ in space, but breaks local revertibility. The version of our algorithm with this modification is Theorem 18.

1.5 Our Technique: Random Walks

In this introduction, for simplicity, we will assume the graph $G$ is acyclic and 2-outregular, with each vertex having a $0$ edge and $1$ edge. We will determine the probability that a random walk from $s$ ends at $t$ with additive error at most $\varepsilon$ .

Allocate one bit of the catalytic tape for each vertex. For vertex $v$ , denote this register $R_{v}$ . Run $K=\lceil 2m/\varepsilon\rceil$ walks from $s$ as follows. At vertex $v$ , we take the edge labeled with the current value of $R_{v}$ , then set $R_{v}\leftarrow 1-R_{v}$ . In this way, if we examine walks reaching $v$ over the course of the $K$ walks, the next edges taken are $0,1,0,1,\dotsc$ or $1,0,1,0,\dotsc$ . The top row of Figure 2 shows an example of this process, with the bits of the catalytic tape drawn directly on the corresponding vertices as $\uparrow$ or $\downarrow$ .

Now we can argue that the number of visits to each vertex approximately equals the expected number of visits if we had done a truly random walk. A common way to prove this kind of result is with a “local consistency check” – see for example Nisan’s Lemma 2.6 [9, 3].

The general idea is that if every vertex is given a pseudorandom bit of $0$ approximately as many times as it is given a $1$ , then each vertex is visited approximately the right number of times. Our version of this argument appears in the proof of Lemma 25. By a careful analysis we show that the number of visits to each vertex is within $2m$ of its expected value, regardless of the number of simulations. Thus after $K$ simulations, we obtain additive error at most $2m/K\leq\varepsilon$ .

$\blacktriangleright$ Remark 7.

Our runtime is linear in $1/\varepsilon$ , which is better than the $1/\varepsilon^{2}$ dependence of the algorithm that simply takes true random walks. For some intuition on how the algorithm achieves this, note that for every vertex that has been visited $T$ times, every out-edge is visited $T/d\pm 1$ times, whereas for a true random walk, we would expect a deviation on the order of $T/d\pm\sqrt{T}$ .

Finally, we must restore the catalytic tape. This is done by running the “reverse” of our $K$ simulations. We do not literally walk in reverse; rather, we walk forward as before, but slightly change the way we supply random bits, so that each “reverse” walk exactly undoes the effect of one normal walk. For details, see Algorithm 2 and Corollary 27.

Figure 2: Top row: simulated random walks, using one bit of catalytic space per vertex (shown as

\uparrow

or

\downarrow

) to alternate between random choices. Bottom row: a comparison to a true random walk, illustrating the parts of Definition 22: visit probabilities

p_{v}

(left), visit

c_{v}

and transition

c_{v}^{r}

counts (centre), and errors

e_{v}=|c_{v}-3p_{v}|

,

e_{v}^{r}=|c_{v}^{r}-\frac{3}{2}p_{v}|

(right).

1.6 Summary of Contributions

From a complexity perspective, neither result places new problems in catalytic logspace. However, we view these algorithms as having two main advantages over prior work. First, the techniques are simple and clearly demonstrate the power of catalytic computation. Second, this simplicity allows us to give concrete bounds on their resource usage (both catalytic space and time). We view algorithms in catalytic space as worthy of further study; we have no reason to suspect our runtimes are optimal. In addition, we are interested in whether other catalytic algorithms can be made locally revertible.

2 Preliminaries

We denote $\mathbf{N}=\{0,1,2,\dotsc\}$ the natural numbers, and for $n\in\mathbf{N}$ we denote $[n]=\{0,1,\dotsc,n-1\}$ the natural numbers less than $n$ .

For a vertex $v$ in a directed graph, $\operatorname{d_{\mathrm{in}}}(v)$ is the number of incoming and $\operatorname{d_{\mathrm{out}}}(v)$ is the number of outgoing edges.

We require a very weak bound on the number of paths in a graph:

Fact 8.

For an $n$ -vertex graph (possibly with self-loops), the number of length- $T$ paths between any two vertices is at most $P_{n}=n^{T}$ .

We assume basic familiarity with word-RAM and catalytic machines. For concreteness, we give a (not entirely formal) definition of catalytic RAM machines.

Definition 9 (Catalytic RAM Machine).

We say $\mathcal{A}$ is a catalytic RAM machine that computes a function $f:\{0,1\}^{*}\rightarrow\{0,1\}^{*}$ using $T(n)$ time, $S(n)$ workspace, and $W(n)$ catalytic space if it works as follows. The machine is given read-only access to $x$ , read-write access to $S(|x|)$ bits of workspace, read-write access to a catalytic tape $R$ of length $W(|x|)$ in initial configuration $\tau$ , and write-only access to an output tape.

Furthermore, we allow the algorithm query access to the catalytic tape, in that it can read and write a specified bit in constant time after writing the index of this bit to a dedicated query tape. For every $x$ and $\tau$ , we have that the machine halts in at most $T(|x|)$ steps with $f(x)$ on the output tape and the catalytic tape restored to $\tau$ .

Our definition is not powerful enough to allow analysis of runtimes without polylog factors from query overheads, and we do not attempt this.

2.1 Catalytic Registers

It is often convenient for an algorithm to view its catalytic space as consisting of registers $R_{1},R_{2},\dotsc$ for doing arithmetic over some modulus $q$ . If $q$ is a power of two, this is straightforward: allocate $\log q$ bits per register. However, our faster randomized connectivity algorithms (Theorems 2 and 5) need to work with arbitrary moduli $q$ , which creates a difficulty: if we allocate $\ell=\lceil\log q\rceil$ bits of the catalytic tape to each register, some registers may start with values outside the range $0,\dotsc,2^{\ell}-1$ .

Buhrman, Cleve, Koucký, Loff and Speelman [2, Lemma 15] have a clever solution to this problem which unfortunately is too slow for our purposes. Instead, we do the following.

Choose $\ell$ to be a constant factor larger than $\lceil\log q\rceil$ , and treat the $\ell$ -bit string as an element of $\mathbf{Z}/qd\mathbf{Z}$ , where $d=d(q,\ell)$ is the largest value such that $qd\leq 2^{\ell}$ . We say $R$ is valid for (modulus) $q$ if its initial value is less than $q d$ , and otherwise we say $R$ is invalid.

Our algorithm ensures its registers are valid by applying a shift to all registers simultaneously.

Fact 10.

For an $\ell$ -bit register $R$ with initial configuration $\tau$ , over a uniformly random shift $\beta\in[2^{\ell}]$ , $(\tau+\beta)\bmod 2^{\ell}$ is valid for $q$ with probability greater than $1-1/(d+1)$ .

Each valid register can be decomposed as having value $aq+b$ ; to do arithmetic modulo $q$ , we leave $a$ fixed and only change the $b$ part. It is easy to see these operations can be computed in simultaneous time $\widetilde{O}(\ell)$ and space $O(\log\ell)$ , given $q, d$ as input. For valid registers $R,R^{\prime}$ over modulus $q$ , we let $R\leftarrow R\pm R^{\prime}$ to be this operation.

Now that we can implement registers over arbitrary moduli, the following straightforward lemma lets us use them to check whether counts over a much larger domain are nonzero:

Lemma 11.

Let $V\leq 2^{P}$ be arbitrary. For a uniformly random $r\in[P^{2}]$ , the probability that $V\equiv 0\pmod{r}$ is at most $1-O(1/\log P)$ .

Proof.

Note that $V$ can have at most $P$ distinct prime factors, and for every prime $q$ that is not one of these factors we have that $V\not\equiv 0\pmod{q}$ . Moreover, a random element in $[S]$ is prime with probability $\Omega(1/\log S)$ by the Prime Number Theorem. Thus, if we consider the interval $[P^{2}]$ , this interval contains at least $P^{2}/O(\log P)$ primes, of which at most $P$ divide $V$ , so the probability that we draw a prime that does not divide $V$ is at least

\frac{P^{2}/O(\log P)-P}{P^{2}}=\Omega(1/\log P)\ldotp\

$\hfill\blacktriangleleft$

2.2 Input Representation

Because our catalytic algorithms do not have the space to perform otherwise standard transformations on the graph (for instance, producing an adjacency list given an adjacency matrix), we must be careful with how they access the input. We adopt the model of oracle access, which is common in sublinear and local models. We say we have oracle access to a graph $G$ if its vertex set is $[n]$ for some $n\in\mathbf{N}$ , and for any $v\in[n]$ we can make the following queries:

$\blacksquare$

$\operatorname{InDeg}_{G}(v)$ (resp. $\operatorname{OutDeg}_{G}(v)$ ) returns the in-degree $\operatorname{d_{\mathrm{in}}}(v)$ (resp. out-degree $\operatorname{d_{\mathrm{out}}}(v)$ ).
$\blacksquare$

$\operatorname{InNbr}_{G}(v,i)$ (resp. $\operatorname{OutNbr}_{G}(v,i)$ ) returns the $i$ th in-neighbor (resp. out-neighbor) of $v$ , or $\perp$ if this does not exist.

Our connectivity algorithms only use in-edge access to the graph, and our random walk algorithms only use out-edge access.

For the locally revertible connectivity algorithm (Theorem 5), we use that given a graph, we can provide oracle access to a modified graph with bounded in-degree:

Lemma 12.

Given oracle access to a directed graph $G$ with $n$ vertices and $m$ edges, where every vertex has in-degree at most $n$ , there is a simulation of an oracle for a graph $G^{\prime}$ on $n^{\prime}=O(n^{2})$ vertices with the following properties:

$\blacksquare$

The simulation can answer queries in $O(\log n)$ space and $O(\log n)$ time, with the exception of $\operatorname{OutNbr}_{G^{\prime}}$ queries.
$\blacksquare$

The maximum in-degree is $2$ .
$\blacksquare$

The diameter is $\widetilde{O}(n)$ .
$\blacksquare$

For vertices $s,t\in[n]$ , there is an $s\rightarrow t$ path in $G$ if and only if there is an $s\rightarrow t$ path in $G^{\prime}$ . (We have $[n]\subseteq[n^{\prime}]$ , so integers $s, t$ representing vertices of $G$ also represent vertices of $G^{\prime}$ .)

All but $O(m)$ of the vertices of $G^{\prime}$ are isolated (no in- or out-edges), and there is an algorithm to list all non-isolated vertices in $O(\log n)$ space and $\widetilde{O}(m+n)$ time.

We defer the proof to the full version of this paper.

3 Deciding Graph Connectivity

We state our first algorithm, which requires one register per vertex and timestep (but permits local revertibility).

Theorem 13.

There is a catalytic logspace algorithm that, given $\ell,q,T\in\mathbf{N}$ and a graph $G$ with $n$ vertices and $m$ edges and vertices $s, t$ , and $\ell$ -bit registers $R_{i,u}$ for $i\in\{0,\ldots,T\}$ and $u\in V$ that are valid for modulus $q$ (Section 2.1), returns

(\#\text{of $s\rightarrow t$ paths of length $T$})\bmod q\ldotp

Moreover, the algorithm runs in time $\widetilde{O}(\ell^{2}\cdot T\cdot(m+n))$ , and is locally revertible in time $\widetilde{O}(\ell\cdot d_{\max})$ , where $d_{\max}$ is the maximum in-degree of $G$ .

Proof.

We first implicitly lift $G=(V,E)$ to a layered graph on $(n+1)n$ vertices, defined as follows. We let the vertex set be $\{0,\ldots,n\}\times V$ , and the edge set be

E^{\prime}=\{((i,v),(j,u)):j=i+1\text{ and }(v,u)\in E\}.

For every vertex $a=(i,v)$ , let $R_{a}$ be the corresponding register with initial value $\tau_{a}$ .

We then describe the basic algorithm. For an edge $a=(i,u),b=(i+1,v)$ , we let an edge push (resp. reverse edge push) be the update where we set

R_{b}\leftarrow R_{b}+R_{a}\quad\text{(resp.\ }R_{b}\leftarrow R_{b}-R_{a}% \text{)}

where the arithmetic operations are defined as in Section 2.1.

We let $\textsc{layerPush}_{i}$ (resp. $\textsc{revLayerPush}_{i}$ ) be the operation where we perform an edge push (resp. reverse edge push) on every edge from layer $i$ to layer $i+1$ . We do this by iterating over vertices $v$ , and using $\operatorname{InNbr}_{G}(v)$ oracle queries to determine the in-neighbors of $v$ , and then pushing along these edges.

Finally, let $\textsc{incStart}(b)$ be the operation where we set

R_{(0,s)}\leftarrow R_{(0,s)}+b.

For each $b$ , we define the push and reverse sequence

\mathcal{P}_{b}=(\textsc{incStart}(b),\textsc{layerPush}_{0},\ldots,\textsc{% layerPush}_{T-1})

\mathcal{R}_{b}=(\textsc{revLayerPush}_{T-1},\ldots,\textsc{revLayerPush}_{0},% \textsc{incStart}(-b)).

First, note that the catalytic tape is easy to reset:

Claim 14.

For every value $b$ and register $R_{a}$ , after executing $(\mathcal{P}_{b},\mathcal{R}_{b})$ we have that $R_{a}=\tau_{a}$ .

Proof.

It clearly suffices to prove that $\textsc{layerPush}_{i},\textsc{revLayerPush}_{i}$ preserve the tape configuration. This follows directly from the linearity of addition and the definition of both operations. $\hfill\vartriangleleft$ Finally, the difference in the final values at a register with $b=\{0,1\}$ is exactly the number of paths from $s$ to this register:

Lemma 15.

For every $i, v, b$ , let $\alpha_{(i,v),b}$ be the value of $R_{(i,v)}$ after $\mathcal{P}_{b}$ . Then $\alpha_{(i,v),1}-\alpha_{(i,v),0}$ is exactly the number of length $i$ $s\rightarrow v$ paths in $G$ , modulo $q$ .

Proof.

Note that $\alpha_{(i,v),b}$ is the value of $R_{(i,v)}$ after

\textsc{incStart}(b),\textsc{layerPush}_{0},\ldots,\textsc{layerPush}_{i-1}

since subsequent operations in $\mathcal{P}_{b}$ do not write to $R_{(i,v)}$ .

Suppose the claim holds for every vertex in layer $i-1$ . Next, fix an arbitrary vertex $w=(i,v)$ , and let $(u_{1},\ldots,u_{r})\subseteq[V]$ be the in-neighbors of $v$ in $G$ . Note that every length- $i$ path from $s$ to $v$ decomposes as

(s,\ldots,u_{j})(u_{j},v)

for some unique $u_{j}$ , so the paths are in one-to-one correspondence with length $i-1$ paths from $s$ to $u_{j}$ for some $j$ .

Finally, recall that $w$ has in-neighbors

a_{1}=(i-1,u_{1}),\ldots,a_{r}=(i-1,u_{r}).

and observe that

\alpha_{w,b}\equiv\tau_{w}+\sum_{j\in[r]}\alpha_{a_{j},b}\pmod{q}

and hence

\alpha_{w,1}-\alpha_{w,0}\equiv\sum_{j\in[r]}(\alpha_{a_{j},1}-\alpha_{a_{j},0% })\pmod{q}

and so by the inductive hypothesis we are done. $\hfill\blacktriangleleft$ Then the final algorithm is straightforward. We determine and print $\alpha_{(n,t),1}-\alpha_{(n,t),0}\pmod{q}$ . We compute this value by comparing the $\ell$ -bit registers bit by bit, each time using the sequence $\mathcal{P}_{b},\mathcal{R}_{b}$ with alternating values of $b$ .

Lemma 16.

The algorithm runs in $\widetilde{O}(\ell^{2}T\cdot(n+m))$ time.

Proof.

Given an edge $e$ and layer $i$ , pushing along this edge takes time $\widetilde{O}(\ell)$ , and hence a layer push takes time $\widetilde{O}((m+n)\cdot\ell)$ . Therefore executing $\mathcal{P}_{b}$ and $\mathcal{R}_{b}$ takes time $\widetilde{O}(T\cdot(n+m)\ell)$ . Finally, we invoke both routines $\ell$ times to compute the final value, so the total runtime is as claimed. $\hfill\blacktriangleleft$

Finally, we show how the algorithm is locally revertible.

Lemma 17.

The algorithm is locally revertible in time $\widetilde{O}(\ell\cdot d_{\max})$ .

Proof.

Suppose we receive a query to return $\tau_{a}$ , the initial value of the register $R_{a=(i,v)}$ . Let $u_{1},\ldots,u_{r}$ be the in-neighbors of $v$ , which we can enumerate over using the oracle for $G$ . The register $R_{a}$ is either in its initial state (in which case we can return its current value without modifying the tape), or some push sequence $\mathcal{P}_{b}$ has been executed. In that case, the current value of $R_{a}$ is

	$\displaystyle R_{a}$	$\displaystyle=\alpha_{a,b}$
		$\displaystyle=\tau_{a}+\sum_{j\in[r]}\alpha_{(i-1,u_{j}),b}$
		$\displaystyle=\tau_{a}+\sum_{j\in[r]}R_{(i-1,u_{j})}$

where the second equality follows from the definition of $\mathcal{P}_{b}$ , and the third follows from the fact that we do not modify registers in layer $i-1$ before reverting layer $i$ to the original register configuration. Thus, we can recover $\tau_{a}$ by enumerating over the in-neighbors of $v$ and computing

R_{a}-\sum_{j\in[r]}R_{(i-1,u_{j})}=\tau_{a}.

Afterwards, we revert $R_{a}$ to $\alpha_{a,b}$ and continue execution as before. The time for the query is bounded by $\widetilde{O}(\ell\cdot r)=\widetilde{O}(\ell\cdot d_{\max})$ as claimed. $\hfill\blacktriangleleft$ This completes the proof of the desired properties. $\hfill\blacktriangleleft$

Next, we present a version of the algorithm that avoids lifting the graph, at the cost of not permitting local revertibility. In this case, we do not compute the number of $s\rightarrow t$ paths mod the register size, simply a number that is nonzero if a path exists.

Theorem 18.

For every $T\in\mathbf{N}$ and simple directed graph $G$ with $n$ vertices and $m$ edges and vertices $s, t$ , there is $\zeta_{G,s,t}\in\mathbf{N}$ where:

$\blacksquare$

$\zeta_{G,s,t}\leq(n+1)^{T}$ , and
$\blacksquare$

$\zeta_{G,s,t}$ is nonzero if and only if there is an $s\rightarrow t$ path in $G$ of length at most $T$ .

Moreover, there is a catalytic logspace algorithm that, given $\ell,q,T\in\mathbf{N}$ and a graph $G$ and vertices $s, t$ , and $\ell$ -bit registers $R_{\sigma,v}$ for $\sigma\in\{0,1\}$ and $v\in V$ that are valid for modulus $q$ , returns

\zeta_{G,s,t}\bmod q\ldotp

Moreover, the algorithm runs in time $\widetilde{O}(\ell^{2}\cdot T\cdot(n+m))$ .

Proof.

We describe the basic algorithm, which is like that of Theorem 13 but uses fewer registers. For each vertex $v$ , the two registers $R_{0,v},R_{1,v}$ replace the $T+1$ registers $R_{i,v}$ from the previous algorithm.

We define layer push operations given a parity value $\sigma\in\{0,1\}$ . For $(u,v)\in E$ in some fixed order (where we add dummy edges $(u,u)$ for every $u$ ), set

R_{\neg\sigma,v}\leftarrow R_{\neg\sigma,v}+R_{\sigma,u}.

and then set $\sigma\leftarrow\neg\sigma$ . We define a reverse layer push as, for the same set of edges, setting $\sigma\leftarrow\neg\sigma$ and then

R_{\neg\sigma,v}\leftarrow R_{\neg\sigma,v}-R_{\sigma,u}\ldotp

Next let $\textsc{incStart}(b)$ be the operation where we set

R_{0,s}\leftarrow R_{0,s}+b.

For each $b$ , we initialize $\sigma=0$ and define the push and reverse sequence:

\mathcal{P}_{b}=(\textsc{incStart}(b),\textsc{layerPush}^{(n)}),\qquad\mathcal% {R}_{b}=(\textsc{revLayerPush}^{(n)},\textsc{incStart}(-b)).

By essentially the same argument as Claim 14, we have that after executing $(\mathcal{P}_{b},\mathcal{R}_{b})$ for $b\in\{0,1\}$ , every register $R_{\sigma,v}$ is reset to its initial configuration $\tau_{\sigma,v}$ . The runtime is straightforward from the description.

Finally, we must prove correctness. For every $i$ , let $\sigma_{i}\in\{0,1\}$ be the parity of the registers pushed to in phase $i$ (and note that $\sigma_{0}=0$ ).

Definition 19.

For every $\sigma\in\{0,1\}$ , vertex $v$ , and integer $i\geq-1$ , define $\zeta_{(\sigma,v),i}$ recursively as follows.

$\blacksquare$

$\zeta_{(1,v),-1}=0$ for all $v$ .
$\blacksquare$

$\zeta_{(0,s),0}=1$ and for $v\neq s$ , $\zeta_{(0,v),0}=0$ .
$\blacksquare$

For every $v$ ,

$\zeta_{(\sigma_{i+1},v),i+1}:=\zeta_{(\sigma_{i-1},v),i-1}+\sum_{u:(u,v)\in E}% \zeta_{(\sigma_{i},u),i}.$

We prove that these values are exactly the register difference after the pushes:

Lemma 20.

Let $\alpha_{(\sigma_{i},v),i,b}$ be the value of $R_{\sigma_{i},v}$ after $\textsc{incStart}(b),\textsc{layerPush}^{(i)}$ . For every $v\in V$ we have

\alpha_{(\sigma_{i},v),i,1}-\alpha_{(\sigma_{i},v),i,0}\equiv\zeta_{(\sigma_{i% },v),i}\pmod{q}.

Proof.

For convenience, we define $\alpha_{(1,v),-1,b}$ to be the initial value of $R_{1,v}$ for each vertex $v$ . We prove the lemma by induction.

For the base cases, we have that

\alpha_{(1,v),-1,1}-\alpha_{(1,v),-1,0}=0=\zeta_{(0,v),-1}

\alpha_{(0,v),0,1}-\alpha_{(0,v),0,0}=\mathbb{I}[v=s]=\zeta_{(0,v),0}

Now assume this holds for $i$ and $i-1$ and consider the $i+1$ st push. WLOG suppose $\sigma_{i+1}=0$ . For $v\in V$ we have

\alpha_{(0,v),i+1,b}\equiv\alpha_{(0,v),i-1,b}+\sum_{u:(u,v)\in E}\alpha_{(1,u% ),i,b}\pmod{q}

and hence

\alpha_{(0,v),i+1,1}-\alpha_{(0,v),i+1,0}\equiv\zeta_{(0,v),i-1}+\sum_{u:(u,v)% \in E}\zeta_{(1,u),i}\equiv\zeta_{(1,v),i+1}\pmod{q}.\

$\hfill\blacktriangleleft$ Then a simple inductive argument proves that $\zeta_{(\sigma_{i},v),i}\leq(n+1)^{i}$ , and moreover that the set of $v$ for which $\zeta_{(\sigma_{i},v),i}>0$ is exactly those $v$ with an $s\rightarrow v$ path of length at most $i$ . $\hfill\blacktriangleleft$

Putting it all together

We then use these results to prove the main theorems.

For the deterministic algorithm, we choose the register size and modulus $q$ large enough so that the count of paths mod $q$ is equal to the count of paths. See 1

Proof.

We initialize $2n$ registers $\{R_{\sigma,v}\}_{\sigma\in\{0,1\},v\in V}$ each of size $\ell=\lceil\log((n+1)^{n})+1\rceil$ and set $q=2^{\ell}$ . Since we chose $q=2^{\ell}$ , all registers are valid no matter their initial configuration, so we immediately invoke Theorem 18 with $T=n$ . If the value obtained is nonzero, we return that there is a path, and otherwise return that there is no path. The runtime is immediate from the choice of $\ell$ and $T$ . $\hfill\blacktriangleleft$

We now give the randomized algorithm. See 2

Proof.

Let $B_{n}=(n+1)^{n}+1$ .

The Algorithm.

For $I=O(\log n)$ iterations (where the specific constant is to be chosen later), we proceed as follows. We initialize $2n$ registers $\{R_{\sigma,v}\}_{\sigma\in\{0,1\},v\in V}$ , each of size

\ell=5\lceil\log B_{n}\rceil.

We draw a random modulus $q\in[\log^{2}B_{n}]$ and store in on the worktape. Let $d$ be the largest value such that $qd\leq 2^{\ell}$ (which we can compute in time $\operatorname{polylog}(n)$ and store on the worktape). We have that

d\geq\frac{2^{\ell}}{2q}>n^{3}

Next, we draw a random shift $\beta\in[2^{\ell}]$ and store it on the worktape. We add $\beta$ to each register $R_{\sigma,v}$ with initial configuration $\tau_{\sigma,v}$ and verify that $\tau_{\sigma,v}+\beta$ is valid for $q$ . If not, we subtract $\beta$ from all registers and abort (and return $\perp$ ). Otherwise, we invoke Theorem 18 with this register set and $T=n$ . Let the returned value be $\zeta$ . We first subtract $\beta$ from all registers. Then, if $\zeta\neq 0$ , we return that there is a path, and otherwise proceed to the next iteration. If we exhaust all iterations, we return that there is not a path.

Success Probability.

We first argue that the algorithm does not abort with high probability. There are $2n$ registers, each of which we shift $O(\log n)$ times. By Fact 10, the probability that any such shift results in an invalid configuration is at most $2/n^{3}$ , so a union bound completes the proof.

Next, note if $\zeta_{G,s,t}=0$ , the algorithm clearly never returns there is a path. Otherwise, for each $q$ drawn by the algorithm, by Lemma 11 the probability that $\zeta_{G,s,t}\equiv 0\pmod{p}$ is at most $(1-O(1/\log\log B_{n}))=(1-1/O(\log n))$ , and hence choosing $I=O(\log n)$ sufficiently large, we obtain that with probability at least $1-1/100$ there is some iteration where we detect a nonzero number of paths, and thus succeed.

Finally, runtime and space consumption follow directly from the description of the algorithm. $\hfill\blacktriangleleft$

Finally, we finish the proof of the locally revertible algorithm. See 5

Proof.

We first modify the input graph $G$ by simulating access to the graph $G^{\prime}$ using the query oracle of Lemma 12. Let $n^{\prime}=O(n^{2})$ be the number of vertices of $G^{\prime}$ , let $n^{\prime\prime}=O(m)$ be the number of non-isolated vertices, let $T=\widetilde{O}(n)$ be its diameter, and recall that (after virtually adding a self-loop on $t$ ) it has maximum in-degree $3$ . Let $p_{n^{\prime}}=\lceil\log P_{n^{\prime}}\rceil$ be the logarithm of the bound on the number of paths in $G^{\prime}$ of Fact 8.

The Algorithm.

For $I=O(\log n)$ iterations (where the specific constant is to be chosen later), we proceed as follows. First, we initialize the registers we will use by adding a random shift as described in Section 2.1. We will have a register corresponding to each layer and vertex in $G^{\prime}$ , indexed as

(i,v)\in\{0,\ldots,T\}\times[n^{\prime}]\ldotp

We allocate $n^{3}$ total registers on the catalytic tape corresponding to these vertices, but we only initialize the $Tn^{\prime\prime}=\widetilde{O}(nm)$ registers which corresond to non-isolated vertices of $G^{\prime}$ . (Recall Lemma 12 gives an algorithm for enumerating these vertices in $\widetilde{O}(m+n)$ time, amounting to $\widetilde{O}(n(m+n))$ time for $n$ layers.) Call a register relevant if it corresponds to $(i,v)$ where $v$ is a non-isolated vertex or $v\in\{s,t\}$ .

Each register has size

\ell=5\lceil\log p_{n^{\prime}}\rceil\ldotp

We draw a random modulus $q\in[p_{n^{\prime}}^{2}]$ and store in on the worktape. Let $d$ be the largest value such that $qd\leq 2^{\ell}$ (which we can compute in time $\operatorname{polylog}(n)$ and store on the worktape). We have that

d\geq\frac{2^{\ell}}{2q}\geq\frac{{m}^{3}}{2}.

Next, we draw a random shift $\beta\in[2^{\ell}]$ and store it on the worktape. We add $\beta$ to each relevant register $R_{a}$ with initial configuration $\tau_{a}$ , and then verify that each $\tau_{a}+\beta$ is valid for $q$ . If not, we first subtract $\beta$ from all relevant registers, and then abort (and return $\perp$ ). Otherwise, we invoke Theorem 13 with

G=G^{\prime},\qquad T=T

except we modify it to only push values from relevant registers. Let the returned value be $\alpha$ . We restore the catalytic tape by subtracting $\beta$ from all relevant registers. Then, if $\alpha\neq 0$ , we return there is a path, and otherwise proceed to the next iteration. If we exhaust all iterations, we return that there is not a path.

Success Probability.

We first argue that the algorithm does not abort with high probability. Note that there are $\widetilde{O}(nm)$ registers, each of which we shift $O(\log n)$ times. By Fact 10, the probability that any such shift results in an invalid configuration is at most $4/m^{3}$ , so a union bound completes the proof.

Next, let $V$ be the total number of length- $n$ paths from $s$ to $t$ in the modified graph. If $V=0$ , the algorithm clearly never returns there is a path. Otherwise, for each $q$ drawn by the algorithm, by Lemma 11 the probability that $V\equiv 0\pmod{p}$ is at most $(1-O(1/\log p_{n^{\prime}}))=(1-1/O(\log n))$ , and hence choosing $I=O(\log n)$ sufficiently large, we obtain that with probability at least $1-1/100$ there is some iteration where we detect a nonzero number of paths, and thus succeed.

Finally, runtime and space consumption follow directly from the description of the algorithm.

Local Revertibility.

Finally, we argue that the algorithm is locally revertible. Given a query on register $a$ , we query the local revertibility routine of Theorem 13 on this register. Since we initialized the algorithm of Theorem 13 with $R_{a}$ in configuration $\tau_{a}+\beta$ , it returns this value, and we return $\tau_{a}$ by subtracting the stored shift $\beta$ . Finally, since $G^{\prime}$ has constant degree, the time is as claimed. $\hfill\blacktriangleleft$

4 Estimating Random Walks

The bulk of our proof of Theorem 6 is a technique for simulating random walks on acyclic graphs:

Theorem 21 (random walk on a DAG).

There is an algorithm which, given a directed acyclic graph $G$ with $n$ vertices and $m$ edges, together with vertex $s$ , sink vertex $t$ , and parameter $\varepsilon>0$ , returns $\rho$ such that

\left|\rho-\Pr[\text{random walk from $s$ reaches $t$}]\right|\leq\varepsilon\ldotp

The algorithm runs in time $\widetilde{O}(nm/\varepsilon)$ . It uses $O(\log(nm/\varepsilon))$ workspace and $\widetilde{O}(n\log(m/\allowbreak\varepsilon))$ catalytic space; the algorithm is guaranteed to restore the catalytic tape to its initial state as long as the input is valid – in particular, the graph $G$ has no cycles.

(This version of our algorithm has the curious property that it can be tricked into making irreversible changes to its catalytic tape if $G$ has cycles. If this is undesirable, the algorithm could be changed to require an efficiently checkable proof that $G$ is acyclic, like a topological ordering of its vertices.)

The algorithm is described by $\operatorname{\textnormal{{walk}}}$ (Algorithm 1) and its subroutine $\operatorname{\textnormal{{walk\_once}}}$ (Algorithm 2). To prove Theorem 21, we must prove two things for every $G,s,t,\varepsilon$ : in Section 4.2, we show that $\operatorname{\textnormal{{walk}}}(G,s,t,\varepsilon)$ gives the correct output, and in Section 4.3, we show that it restores the catalytic tape at the end of the computation. Section 4.4 ties the proof together and analyzes the time and space used. Section 4.5 proves Theorem 6 by converting any graph into a larger acyclic graph, and then in Section 4.6, we explore what happens if we apply our technique directly to a graph with cycles, skipping the conversion step.

4.1 Registers

The algorithm uses one register $R_{v}$ on the catalytic tape for every vertex $v$ of the graph. We allocate $\ell$ bits to each register, where $\ell=\lceil\log K\rceil$ and $K=\lceil 2m/\varepsilon\rceil$ is the number of simulations run by Algorithm 1. So, each register stores a number in the range $0,\dotsc,2^{\ell}-1$ . We choose this value of $\ell$ so that if we increment the value of a register $K$ times, each time adding one modulo $2^{\ell}$ , there is at most one time when it resets to $0$ instead of increasing by one. Concretely, this is used in the proof of Lemma 23 to bound the error introduced by this reset.

Algorithm 1

\operatorname{\textnormal{{walk}}}(G,s,t,\varepsilon)

. Parameters: graph

G

, source

s

, target

t

, accuracy

\varepsilon

.

Algorithm 2

\operatorname{\textnormal{{walk\_once}}}(G,s,m)

. Parameters: graph

G

, source

s

, mode

m\in\{\textnormal{{forward}},\textnormal{{reverse}}\}

. Returns a sink vertex of

G

. (This algorithm modifies the catalytic tape, so it is not a catalytic algorithm. However, the changes are reversible, so it can be used as a subroutine in a catalytic algorithm.)

4.2 The output is correct

To evaluate how well $\operatorname{\textnormal{{walk}}}$ simulates a random walk on $G$ , we will compare the number of times $\operatorname{\textnormal{{walk\_once}}}$ visits each vertex to the probability a true random walk would reach it. We will argue that for every vertex $v$ , the algorithm splits its time fairly over the $\operatorname{d_{\mathrm{out}}}(v)$ different outgoing edges when it takes a step on line 11, from which it will follow that our simulation is sufficiently accurate.

Throughout this section, fix $G, s, t$ and $\varepsilon$ . Fix an initial content of the catalytic tape $\tau$ , and let $R_{v}$ be the $\ell$ -bit register allocated to vertex $v$ with initial value $\tau_{v}$ .

Let $K=\lceil 2m/\varepsilon\rceil$ as in $\operatorname{\textnormal{{walk}}}$ .

The following definition establishes some notation to help reason about the accuracy of the simulation. It is illustrated in Figure 2.

Definition 22 (visit probability $p_{v}$ , visit count $c_{v}$ , error $e_{v}$ , transition count $c_{v}^{r}$ , transition error $e_{v}^{r}$ ).

Let $p_{v}$ be the probability that a random walk starting at $s$ reaches a vertex $v$ .

Let $c_{v}$ be the number of times $\operatorname{\textnormal{{walk\_once}}}$ visits $v$ during the forward phase of $\operatorname{\textnormal{{walk}}}$ (lines 3–8). (A “visit” to the vertex stored in the variable $v$ occurs whenever $\operatorname{\textnormal{{walk\_once}}}$ evaluates the while loop condition on line 3.)

Define the error $e_{v}=|c_{v}-Kp_{v}|$ .

For $r\in[\operatorname{d_{\mathrm{out}}}(v)]$ , let $c_{v}^{r}$ be the number of those visits for which the variable $r$ had the given value on line 11 of $\operatorname{\textnormal{{walk\_once}}}$ (so $c_{v}=\sum_{r=0}^{\operatorname{d_{\mathrm{out}}}(v)-1}c_{v}^{r}$ unless $v$ is a sink). $c_{v}^{r}$ counts transitions where the algorithm followed the $r$ -th outgoing edge from $v$ .

Define the transition error $e_{v}^{r}=|c_{v}^{r}-Kp_{v}/\operatorname{d_{\mathrm{out}}}(v)|$ .

Lemma 23.

For every vertex $v$ and $r\in[\operatorname{d_{\mathrm{out}}}(v)]$ , $e_{v}^{r}\leq 2+e_{v}/\operatorname{d_{\mathrm{out}}}(v)$ .

Proof.

Let us temporarily imagine the register $R_{v}$ always stores a value in $[\operatorname{d_{\mathrm{out}}}(v)]$ , and that each time $\operatorname{\textnormal{{walk\_once}}}$ visits $v$ , line 6 increments it as $R_{v}\leftarrow(R_{v}+1)\bmod\operatorname{d_{\mathrm{out}}}(v)$ instead of incrementing modulo $2^{\ell}$ . This causes the value $r$ to cycle through the values $0,\dotsc,\operatorname{d_{\mathrm{out}}}(v)-1$ , so that on the $t$ -th visit to $v$ , $r=(\tau_{v}+t-1)\bmod\operatorname{d_{\mathrm{out}}}(v)$ , where $\tau_{v}$ is the starting value of $R_{v}$ from the catalytic tape. As a result, any two transition counts must differ by at most one:

|c_{v}^{r}-c_{v}^{r^{\prime}}|\leq 1\hbox to0.0pt{\qquad\text{(pretending $R_{% v}\in[\operatorname{d_{\mathrm{out}}}(v)]$).}\hss}

(1)

In fact, $R_{v}$ cycles through the values $0,\dotsc,2^{\ell}$ . As a result $r$ cycles through the values $0,\dotsc,\operatorname{d_{\mathrm{out}}}(v)-1$ in order, with one exception: if register $R_{v}$ cycles from $2^{\ell-1}$ to $0$ , then the cycle is interrupted. Since $2^{\ell}\geq K$ , this can happen at most once. So, instead of Equation 1, we have have that

|c_{v}^{r}-c_{v}^{r^{\prime}}|\leq 2\ldotp

Since $c_{v}=\sum_{r=0}^{\operatorname{d_{\mathrm{out}}}(v)-1}c_{v}^{r}$ , it follows that

\left|c_{v}^{r}-\frac{c_{v}}{\operatorname{d_{\mathrm{out}}}(v)}\right|=\left|% c_{v}^{r}-\sum_{r^{\prime}=0}^{\operatorname{d_{\mathrm{out}}}(v)-1}\frac{c_{v% }^{r^{\prime}}}{\operatorname{d_{\mathrm{out}}}(v)}\right|\leq\frac{1}{% \operatorname{d_{\mathrm{out}}}(v)}\sum_{r^{\prime}=0}^{\operatorname{d_{% \mathrm{out}}}(v)-1}|c_{v}^{r}-c_{v}^{r^{\prime}}|<2\ldotp

and so

e_{v}^{r}=\left|c_{v}^{r}-\frac{Kp_{v}}{\operatorname{d_{\mathrm{out}}}(v)}% \right|\leq\left|c_{v}^{r}-\frac{c_{v}}{\operatorname{d_{\mathrm{out}}}(v)}% \right|+\left|\frac{c_{v}}{\operatorname{d_{\mathrm{out}}}(v)}-\frac{Kp_{v}}{% \operatorname{d_{\mathrm{out}}}(v)}\right|<2+\frac{e_{v}}{\operatorname{d_{% \mathrm{out}}}(v)}\ldotp\

$\hfill\blacktriangleleft$

Lemma 24.

Let $(u_{1},v),\dotsc,(u_{d},v)$ be all edges incoming to a vertex $v$ , where each $(u_{i},v)$ is the $r_{i}$ -th outgoing edge from $u_{i}$ . Then $e_{v}\leq\sum_{i=1}^{d}e_{u_{i}}^{r_{i}}$ .

Proof.

Using the facts that $c_{v}=\sum_{i=1}^{d}c_{u_{i}}^{r_{i}}$ and $p_{v}=\sum_{i=1}^{d}p_{u_{i}}/\operatorname{d_{\mathrm{out}}}(u_{i})$ , we have:

e_{v}=|c_{v}-Kp_{v}|=\left|\sum_{i=1}^{d}(c_{u_{i}}^{r_{i}}-Kp_{u_{i}}/% \operatorname{d_{\mathrm{out}}}(u_{i}))\right|\leq\sum_{i=1}^{m}|c_{u_{i}}^{r_% {i}}-Kp_{u_{i}}/\operatorname{d_{\mathrm{out}}}(u_{i})|=\sum_{i=1}^{d}e_{u_{i}% }^{r_{i}}\

$\hfill\blacktriangleleft$

Lemma 25.

The final value $n_{\mathrm{reach}}/K$ returned by $\operatorname{\textnormal{{walk}}}$ on line 12 is within additive error $\varepsilon$ of the true visit probability $p_{t}$ .

Proof.

We prove this from Lemmas 23 and 24 using an induction argument.

Let $V$ be the set of vertices of $G$ reachable from the start vertex $s$ , and let $v_{0}=s,v_{1},\dotsc,v_{n}=t$ be a topological order on $V$ . That is, for any edge $(u,v)$ , $u$ appears before $v$ in the order.

For $i\in\{0,1,\dotsc,n-1\}$ , consider the cut of $G$ with vertices $v_{0},\dotsc,v_{i}$ on the left and $v_{i+1},\dotsc,v_{n}$ on the right. We are interested in the total error over all the transitions which cross each such cut.

Let $F_{i}\subseteq\{(v,r)\mid v\in V,r\in[\operatorname{d_{\mathrm{out}}}(v)]\}$ be the set of transitions which cross the cut. That is, a pair $(v,r)$ is in $F_{i}$ if $v$ is on the left of the cut and the $r$ -th outgoing edge from $v$ leads to a vertex on the right of the cut. See Figure 3.

Let $D_{i}=\sum_{j=0}^{i}\operatorname{d_{\mathrm{out}}}(v_{j})$ : that is, $D_{i}$ is the number of edges that originate from the left side of the cut (whether or not they cross the cut).

Let $\sigma_{i}=\sum_{(v,r)\in F_{i}}e_{v}^{r}$ , recalling from Definition 22 that $e_{v}^{r}=|c_{v}^{r}-Kp_{v}/\operatorname{d_{\mathrm{out}}}(v)|$ ). We will show by induction that $\sigma_{i}\leq 2D_{i}$ for all $i$ .

Base case: $\sigma_{0}=\sum_{r=0}^{\operatorname{d_{\mathrm{out}}}(v_{0})}e_{v_{0}}^{r}$ .

We know $c_{v_{0}}=K$ and $p_{v_{0}}=1$ , so $e_{v_{0}}=0$ and so by Lemma 23, $\sigma_{0}\leq 2\operatorname{d_{\mathrm{out}}}(v_{0})$ .

Induction step: Fix $i\in[n-1]$ and assume $\sigma_{i}\leq 2D_{i}$ .

Let $(v_{j_{1}},v_{i+1}),\dotsc,(v_{j_{d}},v_{i+1})$ be the edges incoming to $v_{i+1}$ , where each $(v_{j_{k}},v_{i+1})$ is the $r_{k}$ -th outgoing edge from $v_{j_{k}}$ . Those are the transitions that contribute to $\sigma_{i}$ but not $\sigma_{i+1}$ , so we have $\sigma_{i+1}=\sigma_{i}+\sum_{r=0}^{\operatorname{d_{\mathrm{out}}}(v_{i+1})-1% }e_{v_{i+1}}^{r}-\sum_{k=1}^{d}e_{v_{j_{k}}}^{r_{k}}$ . From Lemma 23, we have

\sum_{r=0}^{\operatorname{d_{\mathrm{out}}}(v_{i+1})-1}e_{v_{i+1}}^{r}\leq 2% \operatorname{d_{\mathrm{out}}}(v_{i+1})+e_{v_{i+1}},

and so applying Lemma 24 gives

\sigma_{i+1}\leq\sigma_{i}+2\operatorname{d_{\mathrm{out}}}(v_{i+1})+e_{v_{i+1% }}-\sum_{k=1}^{d}e_{v_{j_{k}}}^{r_{k}}\leq\sigma_{i}+2\operatorname{d_{\mathrm% {out}}}(v_{i+1})\leq 2D_{i+1}

completing the induction.

Figure 3: Two steps in the induction argument in the proof of Lemma 25. On the left,

i=2

and on the right,

i=3

. In each case,

F_{i}

consists of the edges that cross the dashed line, and

\sigma_{i}

is the sum of the errors on those edges.

In particular, $\sigma_{n-1}\leq 2m$ . The corresponding set of edges $F_{n-1}$ are exactly vertex $t$ ’s in-edges. Therefore, by Lemma 24, $e_{t}$ is at most

\sum_{(v,r)\in F_{n-1}}e_{v}^{r}=\sigma_{n-1}\leq 2m

When $\operatorname{\textnormal{{walk}}}$ reaches line 12, $n_{\mathrm{reach}}=c_{t}$ , and so the algorithm returns $c_{t}/K$ . This is within $\varepsilon$ of $p_{t}$ because

\left|\frac{n_{\mathrm{reach}}}{K}-p_{t}\right|=\frac{e_{t}}{K}\leq\frac{2m}{% \lceil 2m/\varepsilon\rceil}\leq\varepsilon\ldotp\

$\hfill\blacktriangleleft$

4.3 The catalytic tape is restored

$\operatorname{\textnormal{{walk}}}$ restores its catalytic tape when it finishes. To see this, the following is enough:

Lemma 26.

Running $\operatorname{\textnormal{{walk\_once}}}(G,s,t,\textnormal{{forward}})$ then $\operatorname{\textnormal{{walk\_once}}}(G,s,t,\textnormal{{reverse}})$ leaves all register values $R_{v}$ with the same values they started with.

Proof.

It is enough to show both calls to $\operatorname{\textnormal{{walk\_once}}}$ visit the same sequence of vertices, since then each register is incremented and decremented the same number of times. (We say $\operatorname{\textnormal{{walk\_once}}}$ “visits” vertex $v$ each time the loop condition on line 3 is evaluated.)

Loosely speaking, this is true because each time $\operatorname{\textnormal{{walk\_once}}}(G,\allowbreak s,\allowbreak% \textnormal{{reverse}})$ decides which outgoing edge $\operatorname{OutNbr}_{G}(v,r)$ to follow, it first (line 8) undoes the change made by $\operatorname{\textnormal{{walk\_once}}}(G,\allowbreak s,\allowbreak% \textnormal{{forward}})$ , and so it ends up choosing the same edge index $r$ . This argument relies on the fact that a single run of $\operatorname{\textnormal{{walk\_once}}}$ never modifies the same register $R_{v}$ more than once, which follows from the fact that $G$ has no cycles.

To make this more precise, let $v_{0},\dotsc,v_{t}$ be the vertices visited by $\operatorname{\textnormal{{walk\_once}}}(G,\allowbreak s,\allowbreak% \textnormal{{forward}})$ , and $v^{\prime}_{0},\dotsc,v^{\prime}_{t^{\prime}}$ be the vertices visited by the subsequent call to $\operatorname{\textnormal{{walk\_once}}}(G,\allowbreak s,\allowbreak% \textnormal{{reverse}})$ . We show by induction that $v_{i}=v^{\prime}_{i}$ for each $i$ , so that in particular the main loop ends at the same sink vertex in each case and so $t=t^{\prime}$ .

To begin with, $v_{0}=v^{\prime}_{0}=s$ . Now assume $v_{i}=v^{\prime}_{i}$ . If $v_{i}$ is a sink, both subroutine calls halt and we are finished. Otherwise, we must show the same value $r$ is chosen both times. Since neither subroutine call made any other changes to $R_{v}$ , when the second subroutine call subtracts one from $R_{v}$ on line 8, it exactly cancels out the only change made by the first subroutine call on line 6, and so the same value $r$ is recovered, and so the same next step is taken: $v_{i+1}=v^{\prime}_{i+1}$ . $\hfill\blacktriangleleft$

Corollary 27.

$\operatorname{\textnormal{{walk}}}$ leaves its catalytic tape unchanged.

Proof.

This is the same as saying the final values of all registers $R_{v}$ equal the initial values.

By induction on $K$ , we can see that $K$ calls to $\operatorname{\textnormal{{walk\_once}}}(G,s,\textnormal{{forward}})$ followed by $K$ calls to $\operatorname{\textnormal{{walk\_once}}}(G,s,\textnormal{{reverse}})$ has no net effect on the registers $R_{v}$ . For $K=0$ this is clear. Lemma 26 provides the induction step. That is, $K+1$ calls to each can be decomposed as (1) $K$ calls to $\operatorname{\textnormal{{walk\_once}}}(G,s,\textnormal{{forward}})$ , then (2) a single call to each, which by Lemma 26 has no net effect, then (3) $K$ calls to $\operatorname{\textnormal{{walk\_once}}}(G,s,\textnormal{{reverse}})$ . Since (2) has no effect, we are left with $K$ calls each, which by the induction hypothesis have no net effect. $\hfill\blacktriangleleft$

4.4 Proof of Theorem 21 (random walk on a DAG)

Lemma 25 proves that $\operatorname{\textnormal{{walk}}}$ gives a correct answer, and Corollary 27 proves that it restores its catalytic tape. The runtime is dominated by $2K$ calls to $\operatorname{\textnormal{{walk\_once}}}$ , each of which visits each vertex of $G$ at most once. Visiting a vertex means executing one iteration of the main loop of $\operatorname{\textnormal{{walk\_once}}}$ , which takes $\operatorname{polylog}(n+m)$ time, so the total run time is $\widetilde{O}(nK\operatorname{polylog}m)=\widetilde{O}(nm/\varepsilon)$ .⁵⁵5It also uses $\widetilde{O}(n\operatorname{polylog}m)$ time to count the number of edges $m$ in order to compute $K$ . Each register takes $O(\ell)=O(\log(m/\varepsilon))$ bits of the catalytic tape (Section 4.1), for a total of $\widetilde{O}(n\log(m/\varepsilon))$ catalytic space The working memory only includes a constant number of variables $n_{\mathrm{reach}}$ , $v$ , etc, each taking $O(\log(nm/\varepsilon))$ working memory. ∎

4.5 Proof of Theorem 6 (random walk on a general graph)

For convenience, we restate the theorem here: See 6

Proof.

We construct an acyclic graph $G^{\prime}=(V^{\prime},E^{\prime})$ by creating $T+1$ copies of the input graph $G=(V,E)$ and arranging them in layers, with edges going from each layer $i$ to layer $i+1$ . That is, $V^{\prime}=[T+1]\times V$ , and $E^{\prime}=\{((i,u),(i+1,v))\mid t\in[T],(u,v)\in E\}$ .

We then run $\operatorname{\textnormal{{walk}}}$ (Algorithm 1) on the graph $G^{\prime}$ , using start vertex $(0,s)$ and sink vertex $(T,t)$ , and keeping the same parameter $\varepsilon$ . Since a random walk on $G^{\prime}$ from $s$ to a sink is equivalent to a $T$ -step random walk on $G$ , the proof of Theorem 21 implies the algorithm will estimate the probability that a $T$ -step random walk ends at vertex $t$ witin the required additive error bound of $\varepsilon$ . The same proof also implies our algorithm is catalytic.

The space bounds ( $O(\log nmT/\varepsilon)$ working space and $\widetilde{O}(nT\log(m/\varepsilon))$ catalytic space) follow directly from the proof of Theorem 21, since $G^{\prime}$ has $n T$ vertices. The runtime is the time needed to run $\operatorname{\textnormal{{walk\_once}}}$ $K=O(mT/\varepsilon)$ times. Each call to $\operatorname{\textnormal{{walk\_once}}}$ takes $\widetilde{O}(T)$ time, since every walk will have $T$ steps. So, the total runtime is $\widetilde{O}(mT^{2}/\varepsilon)$ . $\hfill\blacktriangleleft$

4.6 What if we don’t eliminate cycles?

The proof of our algorithm’s correctness relies on the graph being acyclic, and so when we are given a general graph, we are forced to pay a penalty in space and time to convert it to an acyclic one. It is tempting to try avoiding the penalty by running the algorithm directly on a graph with cycles.

As it turns out, we end up with an algorithm that is not catalytic, but still accurately simulates a random walk, in the sense that it approaches the graph’s stationary distribution: see Theorem 29.

It would be interesting to try to modify this algorithm to be catalytic without incurring a time or space penalty. This seems challenging, because it is possible to construct a graph that causes $\operatorname{\textnormal{{walk\_once}}}$ to lose information that was stored on the catalytic tape: two different initializations of the registers $R_{v}$ lead to the same final register values, and so recovery is impossible. See Figure 4.

$\begin{matrix}\includegraphics{dagpub-standalone-combined-2025-12-10-11-18-41-% page-9.pdf2svg.svg}\end{matrix}$ $\Rightarrow$ $\begin{matrix}\includegraphics{dagpub-standalone-combined-2025-12-10-11-18-41-% page-10.pdf2svg.svg}\end{matrix}$ $\begin{matrix}\includegraphics{dagpub-standalone-combined-2025-12-10-11-18-41-% page-11.pdf2svg.svg}\end{matrix}$ $\Rightarrow$ $\begin{matrix}\includegraphics{dagpub-standalone-combined-2025-12-10-11-18-41-% page-12.pdf2svg.svg}\end{matrix}$

Figure 4: An example showing why the algorithm of Theorem 29 can’t restore its register values, and so is not catalytic. Two runs of the algorithm for

T^{\prime}=4

steps are shown. The first and third graphs show two different ways to initialize two of the catalytic registers, with

\uparrow,\downarrow

representing the possible values as in Figure 2. The second and fourth graphs show the resulting walks highlighted in blue, and the final values of those registers. The final register values are the same, so the algorithm cannot know which initial values to restore the registers to.

To describe the behaviour of this new algorithm, we first define four terms:

Definition 28 (probability vector, stochastic matrix, stationary distribution, mixing time).

A probability vector $v\in\mathbf{R}^{n}$ is any vector with nonnegative entries and $|v|_{1}=1$ . A matrix $W\in\mathbf{R}^{n\times n}$ is (left) stochastic if every column is a probability vector. The stationary distribution of a stochastic matrix $W\in\mathbf{R}^{n\times n}$ is any probability vector $\pi$ such that $W\pi=\pi$ . We say $W$ mixes in time $T$ with error $\varepsilon$ if the stationary distribution $\pi$ is unique and for every probability vector, $|W^{T}v-\pi|\leq\varepsilon$ . (Here, $W^{T}$ is the $T$ -th power of $W$ , not its transpose.)

We remark that our definition of mixing time implies the Markov chain is ergodic.

Theorem 29.

There is an algorithm which, given a graph $G$ with $n$ vertices and $m$ edges together with vertex $v^{*}$ and parameters $T,\delta\in\mathbf{N}$ , returns a number $\rho$ which approximates the stationary probability at $v^{*}$ in the following sense. If the random walk on $G$ has stationary distribution $\pi$ and mixes in time $T$ with accuracy $\varepsilon$ , then

\left|\rho-\pi(v^{*})\right|\leq\varepsilon+\delta\ldotp

The algorithm runs in time $\widetilde{O}(Tm/\delta)$ and uses space $\widetilde{O}(n)$ .

We defer the proof to the full version of this paper.

5 Future Directions

We hope these examples will inspire others to find new efficient catalytic algorithms for these or other problems. In particular, it would be interesting to avoid the overhead in Theorem 6 from converting to an acyclic graph – Theorem 29 attempts this, but the algorithm fails to be catalytic. For connectivity, our algorithms are all incomparable (in speed, randomness, and revertibility). It would be interesting to obtain a best of both worlds result.

References

[1] Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273–1282, 1998. doi:10.1137/S0097539793283151.
[2] Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, pages 857–866, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2591796.2591874.
[3] Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Adv. Math. Commun., 18:1–32, 2022. doi:10.4086/TOC.2022.V018A021.
[4] James Cook. How to borrow memory. https://www.falsifian.org/blog/2021/06/04/catalytic/.
[5] James Cook, Jiatu Li, Ian Mertz, and Edward Pyne. The structure of catalytic space: Capturing randomness and time via compression. Electronic Colloquium on Computational Complexity: ECCC, 2024.
[6] Dean Doron, Edward Pyne, and Roei Tell. Opening up the distinguisher: A hardness to randomness approach for BPL=L that uses properties of BPL. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 2039–2049, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649772.
[7] Michal Koucký, Ian Mertz, Edward Pyne, and Sasha Sami. Collapsing catalytic classes. Electron. Colloquium Comput. Complex., TR25-019, 2025. URL: https://eccc.weizmann.ac.il/report/2025/019.
[8] Ian Mertz. Reusing space: Techniques and open problems. Bulletin of EATCS, 141(3), 2023. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/780.
[9] Noam Nisan. On read once vs. multiple access to randomness in logspace. Theoretical Computer Science, 107(1):135–144, 1993. doi:10.1016/0304-3975(93)90258-U.
[10] Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In Rahul Santhanam, editor, 39th Computational Complexity Conference (CCC 2024), volume 300 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CCC.2024.4.
[11] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4:177–192, 1970. doi:10.1016/S0022-0000(70)80006-X.

[bib.bib1] [1] Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273–1282, 1998. doi:10.1137/S0097539793283151.

[bib.bib2] [2] Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, pages 857–866, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2591796.2591874.

[bib.bib3] [3] Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Adv. Math. Commun., 18:1–32, 2022. doi:10.4086/TOC.2022.V018A021.

[bib.bib4] [4] James Cook. How to borrow memory. https://www.falsifian.org/blog/2021/06/04/catalytic/.

[bib.bib5] [5] James Cook, Jiatu Li, Ian Mertz, and Edward Pyne. The structure of catalytic space: Capturing randomness and time via compression. Electronic Colloquium on Computational Complexity: ECCC, 2024.

[bib.bib6] [6] Dean Doron, Edward Pyne, and Roei Tell. Opening up the distinguisher: A hardness to randomness approach for BPL=L that uses properties of BPL. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 2039–2049, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649772.

[bib.bib7] [7] Michal Koucký, Ian Mertz, Edward Pyne, and Sasha Sami. Collapsing catalytic classes. Electron. Colloquium Comput. Complex., TR25-019, 2025. URL: https://eccc.weizmann.ac.il/report/2025/019.

[bib.bib8] [8] Ian Mertz. Reusing space: Techniques and open problems. Bulletin of EATCS, 141(3), 2023. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/780.

[bib.bib9] [9] Noam Nisan. On read once vs. multiple access to randomness in logspace. Theoretical Computer Science, 107(1):135–144, 1993. doi:10.1016/0304-3975(93)90258-U.

[bib.bib10] [10] Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In Rahul Santhanam, editor, 39th Computational Complexity Conference (CCC 2024), volume 300 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CCC.2024.4.

[bib.bib11] [11] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4:177–192, 1970. doi:10.1016/S0022-0000(70)80006-X.

Efficient Catalytic Graph Algorithms

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Catalytic space

1.2 Our Results: Connectivity

Theorem 1.

Theorem 2.

▶ Remark 3.

Definition 4.

Theorem 5.

1.3 Our Results: Random Walks

Theorem 6 (random walk on a general graph).

1.4 Our Technique: Connectivity

Improving the runtime with randomness

Local revertibility

Decreasing the number of registers

1.5 Our Technique: Random Walks

▶ Remark 7.

1.6 Summary of Contributions

2 Preliminaries

Fact 8.

Definition 9 (Catalytic RAM Machine).

2.1 Catalytic Registers

Fact 10.

Lemma 11.

Proof.

2.2 Input Representation

Lemma 12.

3 Deciding Graph Connectivity

Theorem 13.

Proof.

Claim 14.

Proof.

Lemma 15.

Proof.

Lemma 16.

Proof.

Lemma 17.

Proof.

Theorem 18.

Proof.

Definition 19.

Lemma 20.

Proof.

Putting it all together

Proof.

Proof.

The Algorithm.

Success Probability.

Proof.

The Algorithm.

Success Probability.

Local Revertibility.

4 Estimating Random Walks

Theorem 21 (random walk on a DAG).

4.1 Registers

4.2 The output is correct

Definition 22 (visit probability pv, visit count cv, error ev, transition count cvr, transition error evr).

Lemma 23.

Proof.

Lemma 24.

Proof.

Lemma 25.

Proof.

Base case: 𝝈𝟎=∑𝒓=𝟎𝐝𝐨𝐮𝐭⁡(𝒗𝟎)𝒆𝒗𝟎𝒓.

Induction step: Fix 𝒊∈[𝒏−𝟏] and assume 𝝈𝒊≤𝟐⁢𝑫𝒊.

4.3 The catalytic tape is restored

Lemma 26.

Proof.

Corollary 27.

$\blacktriangleright$ Remark 3.

$\blacktriangleright$ Remark 7.

Definition 22 (visit probability $p_{v}$ , visit count $c_{v}$ , error $e_{v}$ , transition count $c_{v}^{r}$ , transition error $e_{v}^{r}$ ).

Base case: $\sigma_{0}=\sum_{r=0}^{\operatorname{d_{\mathrm{out}}}(v_{0})}e_{v_{0}}^{r}$ .

Induction step: Fix $i\in[n-1]$ and assume $\sigma_{i}\leq 2D_{i}$ .