Pith. sign in

REVIEW 4 major objections 4 minor 11 references

Efficient Catalytic Graph Algorithms

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Catalytic algorithms that borrow and restore memory solve graph reachability and random-walk estimation with explicit runtime bounds, including a randomized algorithm that uses near-linear catalytic space.

desk verdict New catalytic algorithms with a genuinely elegant random walk simulation and a novel randomized connectivity technique; the main theorem's proof has two large but fixable typos. read the letter →

arxiv 2509.06209 v1 pith:JZ6JP5JM submitted 2025-09-07 cs.DS cs.CC

James Cook , Edward Pyne This is my paper · ORCID
classification cs.DScs.CC MSC 68Q1568R1068W20
keywords catalyticspacelogspaces-tconnectivityrandomwalksgraphalgorithmsrandomizedlocallyrevertiblespace-boundedcomputation
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that catalytic computation—running an algorithm on borrowed memory that must be restored by the end—can solve core graph problems quickly, not just in principle. Previously catalytic algorithms for $s$-$t$ connectivity and random-walk simulation had only unspecified polynomial runtimes. Here the authors give a randomized connectivity algorithm that keeps a small catalytic register for each layer/vertex pair (the optimized version uses just two registers per vertex, alternating by parity), and decides reachability in $\widetilde{O}(nm)$ time with $\widetilde{O}(n)$ catalytic space, plus a deterministic version in $\widetilde{O}(n^3 m)$ time; they describe the randomized version as the first algorithmic use of randomness in catalytic computing. They also give a deterministic random-walk estimator that runs in $\widetilde{O}(mT^2/\varepsilon)$ time and restores its tape. If these bounds hold, catalytic space becomes a much more credible model of borrowing idle memory for fast, short computations.

What carries the argument

The load-bearing mechanism is the edge-push operation on catalytic registers arranged by layer and vertex (the optimized version alternates between two registers per vertex). For each edge $(i,u) \to (i+1,v)$ in a layered graph, the algorithm sets $R_{i+1,v} \leftarrow R_{i+1,v} + R_{i,u}$ modulo $q$; because this is linear, running the pushes once with a $+1$ seed at $s$ and once without, and subtracting, isolates the number of $s$-$t$ paths modulo $q$. A random small modulus $q$ with a random additive shift of all registers lets arbitrary tape contents be treated as valid $q$-ary registers in near-linear time. The random-walk argument uses the same per-vertex register idea as a balancing counter: each visit increments the register, so outgoing edges are used almost equally often, and the local-consistency induction over topological cuts bounds total error by $2m$.

What would settle it

Measure the cost of one addition of two large numbers in the algorithm's register format; if the cost grows much faster than the number of bits, the central runtime claim is false. Or run the random-walk simulator on a small directed acyclic graph with a chosen starting tape and check whether any vertex is visited more often than expected plus $2m$; if so, the $\varepsilon$-additive-error guarantee fails.

Watch

Extended reading notes

Core claim

The central discovery is a simple register-pushing scheme that lets a catalytic machine count and detect paths and random-walk probabilities while still restoring its tape. For connectivity, the graph is lifted into $T+1$ layers; each layer/vertex pair carries a catalytic register (the optimized version keeps two registers per vertex, alternating by parity), and for every edge the algorithm adds the source register into the target register modulo $q$. A $+1$ seed at $s$ gives a final register whose difference from the unseeded run equals the number of length-$T$ paths from $s$ to $t$ modulo $q$. Choosing $q$ at random from a large interval makes a nonzero path count detectable with high probability using $O(\log n)$-bit registers. For random walks, one register per vertex is incremented at each visit, and the next outgoing edge is chosen from the register value modulo the outdegree; a cut-based induction shows every vertex's visit count is within $2m$ of expectation, so $K = \lceil 2m/\varepsilon \rceil$ walks estimate the target probability with additive error at most $\varepsilon$, and the same walks run in reverse restore every register.

Load-bearing premise

The runtime bounds assume the algorithm can add two stored numbers of the size it uses in time roughly proportional to the number of bits in the number; if that addition is slower, every stated runtime gets worse.

Editorial extensions

If this is right

  • Catalytic logspace algorithms for the two canonical complete problems of $\mathsf{NL}$ and $\mathsf{BPL}$ now come with explicit runtimes, so the catalytic-space model can be evaluated as an algorithmic model rather than only a complexity class.
  • The randomized connectivity algorithm shows randomness can serve as a speedup tool inside catalytic computation, not only as a route to class containment.
  • For estimating a $T$-step random walk to inverse-polynomial error $\varepsilon$, the new algorithm runs in nearly linear time $m^{1+o(1)}$ when $T$ and $1/\varepsilon$ are subpolynomial.
  • Local revertibility, defined and achieved in the paper, means a catalytic computation can share borrowed memory with its owner: the original tape contents remain readable with polylogarithmic latency at all times.
  • The randomized algorithm's $\widetilde{O}(n)$ catalytic space is optimal up to polylog factors under conjectured time-space tradeoffs for connectivity, even for algorithms with much larger polynomial runtime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The edge-push counting scheme is essentially a catalytic implementation of iterative path-counting by dynamic programming; the same scheme could be adapted to other dynamic-programming graph properties, such as counting walks with forbidden labels or estimating all-pairs reachability, at similar cost per property.
  • The random-walk simulator suggests a general derandomization recipe for Markov-chain simulation: use one catalytic counter per state to force balanced edge usage, then prove concentration by a local-consistency induction; this may extend to estimating mixing times or hitting probabilities of more general Markov chains.
  • If the register-arithmetic subroutine can be implemented even faster, the connectivity runtime would improve correspondingly; conversely, an instance where modulo-$q$ addition on $\ell$-bit valid registers requires superlinear time would invalidate the stated $\widetilde{O}(nm)$ bound and point to a different trade-off between register size and iteration count.
  • The locally revertible version hints that catalytic memory with read access during computation could be treated as a shared resource, potentially changing how catalytic algorithms are scheduled in memory-constrained systems.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes catalytic logspace algorithms for two graph problems. First, it gives deterministic and randomized catalytic algorithms for s-to-t connectivity: the deterministic algorithm runs in \tilde{O}(n^3 m) time with \tilde{O}(n^2) catalytic space, the randomized algorithm in \tilde{O}(nm) time with \tilde{O}(n) catalytic space, and a locally revertible randomized variant in \tilde{O}(nm) time with \tilde{O}(n^3) catalytic space. The technique is to lift the graph into layers, store one register per vertex (or per vertex and parity), and propagate values by "edge pushes"; a nonzero propagated value modulo a random prime witnesses a path. Second, the paper gives a catalytic algorithm for estimating random-walk hitting probabilities on a DAG in \tilde{O}(nm/\varepsilon) time, extended to general graphs by a layered construction at \tilde{O}(mT^2/\varepsilon) time, and a non-catalytic variant for the stationary distribution. The random-walk analysis is built on a local-consistency argument comparing visit counts with true visit probabilities.

Significance. The results, if correct, would be a meaningful step toward understanding catalytic space from an algorithmic perspective: they give explicit polynomial runtime bounds where previous catalytic algorithms only had unspecified polynomial bounds, they introduce randomization as a tool for algorithmic speedup within CL, and they propose and achieve a notion of local revertibility that strengthens the practical motivation for catalytic computing. The DAG random-walk proof (Lemmas 22-24 and Corollary 26) is a genuine technical contribution: the cut-based error induction is careful and self-contained. The paper is also honest about limitations, notably that cycles break the random-walk restoration property. However, the connectivity section contains several load-bearing errors: the two-parity push in Theorem 17 is irreversible as written, the register size in Theorem 2 contradicts the stated space bound, and a key inequality in Theorem 5 does not follow from the stated parameters. These are fixable within the manuscript's scope, but the central claims are not yet supported by the text.

major comments (4)
  1. [Section 3, Theorem 17] The layer-push operation as displayed is not reversible. The forward update R_{¬σ,v} ← R_{σ,v} + R_{σ,u} overwrites R_{¬σ,v}, discarding its previous value, and the stated reverse operation R_{¬σ,v} ← R_{σ,v} − R_{σ,u} is applied after σ has flipped, so it reads from the newly written parity rather than the original source parity. For the two-vertex graph with one edge (1,2) and initial registers (R_{0,1},R_{0,2},R_{1,1},R_{1,2})=(a,b,c,d), incStart(1) followed by the forward push gives R_{1,2}=b+a+1, and the stated reverse gives R_{0,2}=b+a+1−c, not the initial b. Lemma 19's recurrence α_{(0,v),i+1,b} ≡ α_{(0,v),i−1,b} + Σ_u α_{(1,u),i,b} corresponds instead to the incremental update R_{¬σ,v} ← R_{¬σ,v} + R_{σ,u}. Since Theorems 1, 2, and 5 all invoke Theorem 17 and rely on its tape-restoring property, this needs to be corrected explicitly, for example by adopting the incremental operation.
  2. [Section 3.1, Theorem 2 proof] The register size is set to ℓ = 5⌈log B_n⌉, where B_n = (n+1)^n + 1. Since log B_n = Θ(n log n), the 2n registers occupy Θ(n^2 log n) bits, contradicting the theorem's stated eO(n) catalytic space. Moreover, the algorithm draws a random shift β ∈ [2^ℓ] and stores it on the worktape, which would require Θ(n log n) bits and violate the O(log n) workspace bound. The subsequent inequality d ≥ 2^ℓ/(2q) > n^3 only needs ℓ = Θ(log log B_n); with the displayed value the space claim fails. The proof should be corrected, likely by taking ℓ = 5⌈log log B_n⌉ (or another O(log n) value), and the theorem statement and space analysis updated accordingly.
  3. [Section 3.1, Theorem 5 proof] The claim d ≥ 2^ℓ/(2q) ≥ m^3/2 does not follow from the stated parameters. Here p_{n'} = ⌈log P_{n'}⌉ = ⌈T log n'⌉ = eO(n log n), q ≤ p_{n'}^2, and ℓ = 5⌈log p_{n'}⌉, so 2^ℓ/(2q) = Ω(p_{n'}^3) = n^{O(1)} log^{O(1)} n. When m = Θ(n^2), this is far smaller than m^3/2, so the union-bound estimate in the success-probability argument is not justified as written. The proof should either choose a larger but still O(log n) register size, such as ℓ = Θ(log m + log p_{n'}), or use a different bound on d; with such a change the eO(n^3) space claim would still hold.
  4. [Section 3, Lemma 16] The local revertibility proof only handles two cases: the register is in its initial state, or some complete push sequence P_b has been executed. If a query arrives in the middle of a layerPush, some in-neighbor contributions have not yet been added to R_a, so subtracting the current values of all previous-layer registers does not recover τ_a. Since Definition 4 requires queries at any point during the execution, the proof needs to address partial layer pushes, or the algorithm must be structured to answer queries only at safe points and the theorem statement adjusted accordingly.
minor comments (4)
  1. [Section 4.2, Lemma 24 proof] The induction step says "assume σ_i ≤ 2(i+1)" but the subsequent inequality uses D_i; the intended hypothesis is σ_i ≤ 2D_i. Also, the transitions removed when moving from cut i to cut i+1 are incoming to v_{i+1}, not v_i; the text appears to have an off-by-one typo.
  2. [Section 4, Algorithm 1 and Algorithm 2] Algorithm 1 line 4 calls "walk once(M,x,s,forward)" with undefined variables M and x; it should call "walk once(G,s,forward)". In Algorithm 2, the parameter m for the mode shadows the edge count m used elsewhere; consider renaming the mode to avoid confusion.
  3. [Section 4.6, Algorithm 3] Algorithm 3 line 10 increments R_v modulo 2^ℓ, but the surrounding text states that registers store values in [d_out(v)]. The proof that outgoing-edge counts differ by at most one relies on incrementing modulo d_out(v); the algorithm should be updated accordingly.
  4. [Throughout] There are several typos: in Theorem 2 proof, "store in on the worktape" should be "store it on the worktape"; in Theorem 5 proof, "corresond" should be "correspond"; in Theorem 6, "from s sends at t" should likely be "from s ends at t"; and in Theorem 28 and Algorithm 3, the parameter v* is duplicated in the header.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the connectivity and random-walk algorithms are proved from explicit algorithms and inductive invariants, with no fitted parameters or predictions that reduce to their inputs.

full rationale

The paper's central claims are self-contained derivations. Theorem 17 defines the path-count quantity zeta recursively and then proves by induction (Lemma 19) that the register differences after the push sequence are congruent to zeta modulo q; no quantity in the proof is defined in terms of the target answer, and no empirically fitted value is renamed as a prediction. The randomized modulus and shift arguments (Fact 9 and Lemma 10) are proved in the text from standard number-theoretic facts, and the runtime bounds follow directly from the stated register-size and loop-count parameters. The only self-citation, [Coo25], is disclosed in a footnote as subsumed prior work and is not used to justify any theorem; the random-walk simulation and its correctness proof are given in full in Lemmas 22-26 and Corollary 26. The locally revertible construction and the acyclic-to-general graph reduction for random walks are also proved in place. The skeptical concern about Theorem 17's two-parity reverse operation being irreversible as written is a correctness or proof-gap issue, not a circular reduction of the sort this pass is tasked to detect; accordingly, it does not raise the circularity score.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted to data; the random modulus and random shift are random choices, and the only hand-picked constant is the factor 5 in the register size. The central theorems rely on standard number theory, the catalytic RAM model, and oracle access to the graph.

free parameters (1)
  • constant factor 5 in register size ell = 5
    Chosen by hand in Theorems 2 and 5 to ensure d approximately 2^ell / (2q) exceeds n^3 or m^3/2 for the register validity argument. Not fitted to data; any sufficiently large constant would work.
assumptions (4)
  • standard math Prime Number Theorem
    Used in Lemma 10 to lower bound the probability that a random integer in [P^2] is prime and does not divide V.
  • domain assumption Catalytic RAM model with constant-time query access to the catalytic tape
    Definition 8 models the machine; all runtime and space bounds assume this access model.
  • domain assumption Oracle access to the input graph via InDeg, OutDeg, InNbr, OutNbr queries
    Section 2.2; algorithms do not have space to build adjacency lists, so the oracle model is load-bearing.
  • domain assumption For Theorem 28, the random walk has a unique stationary distribution and mixes in time T with error epsilon
    Definition 27 and the theorem statement; the theorem is conditional on this mixing assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Catalytic Graph Algorithms." pith.science (2026). https://pith.science/paper/JZ6JP5JM

@misc{pith2026250906209,
  author       = {Pith},
  title        = {Pith review of: Efficient Catalytic Graph Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JZ6JP5JM}},
  note         = {Machine review of arXiv:2509.06209}
}
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}( m T^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$.

Figures

Figures reproduced from arXiv: 2509.06209 by the authors.

Figure 1
Figure 1. Pushing values along edges to detect whether a +1 is propagated from s to t. 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, . . . , n} × V , where we place an edge from (i, u) to (i + 1, v) if (u, v) ∈ E. Next, for every v ∈ V an… view at source ↗
Figure 2
Figure 2. Top row: simulated random walks, using one bit of catalytic space per vertex (shown as ↑ or ↓) to alternate between random choices. Bottom row: a comparison to a true random walk, illustrating the parts of Definition 21: visit probabilities pv (left), visit cv and transition c r v counts (centre), and errors ev = |cv −3pv|, e r v = |c r v − 3 2 pv| (right). 1.6 Summary of Contributions From a complexity perspective,… view at source ↗
Figure 3
Figure 3. Converting a graph to an equivalent one with in-degree bounded by 2. Our connectivity algorithms only use in-edge access to the graph, and our random walk algo￾rithms 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 11. Given oracle access to a directed graph G with n vert… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Two steps in the induction argument in the proof of Lemma 24. On the left, i = 2 and on the right, i = 3. In each case, Fi consists of the edges that cross the dashed line, and σi is the sum of the errors on those edges. In particular, σn−1 ≤ 2m. The corresponding set …
Figure 5
Figure 5. Figure 5: An example showing why the algorithm of Theorem 28 can’t restore its register values, and so is not catalytic. Two runs of the algorithm for T ′ = 4 steps are shown. Left: two different ways to initialize two of the catalytic registers, with ↑, ↓ representing the possi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    Computing with a full memory: catalytic space

    Harry Buhrman, Richard Cleve, Michal Kouck\' y , 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, page 857–866, New York, NY, USA, 2014. Association for Computing Machinery

    work page 2014

  2. [2]

    Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Adv. Math. Commun. , 18:1--32, 2022

    work page 2022

  3. [3]

    The structure of catalytic space: Capturing randomness and time via compression

    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

    work page 2024

  4. [4]

    How to borrow memory

    James Cook. How to borrow memory. https://www.falsifian.org/blog/2021/06/04/catalytic/

    work page 2021

  5. [5]

    Another way to show BPL and BPL P

    James Cook. Another way to show BPL and BPL P . Electron. Colloquium Comput. Complex. , TR25-016 , 2025

    work page 2025

  6. [6]

    Opening up the distinguisher: A hardness to randomness approach for BPL=L that uses properties of BPL

    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, page 2039–2049, New York, NY, USA, 2024. Association for Computing Machinery

    work page 2024

  7. [7]

    Collapsing catalytic classes

    Michal Kouck \' y , Ian Mertz, Edward Pyne, and Sasha Sami. Collapsing catalytic classes. Electron. Colloquium Comput. Complex. , TR25-019 , 2025

    work page 2025

  8. [8]

    Reusing space: Techniques and open problems

    Ian Mertz. Reusing space: Techniques and open problems. Bulletin of EATCS , 141(3), 2023

    work page 2023

Show all 11 references
  1. [9]

    On read once vs

    Noam Nisan. On read once vs. multiple access to randomness in logspace. Theoretical Computer Science , 107(1):135--144, 1993

    1993

  2. [10]

    Derandomizing Logspace with a Small Shared Hard Drive

    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 Da...

    2024

  3. [11]

    The complexity of graph connectivity

    Avi Wigderson. The complexity of graph connectivity. In Mathematical Foundations of Computer Science (MFCS) , volume 629 of Lecture Notes in Computer Science , pages 112--132. Springer, 1992

    1992

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.