WorksComputer Science
Catalytic space-efficient algorithms for Distance and Determinant
Abstract
Catalytic computation reuses potentially large but in-use space (or catalytic space) which must be restored to its initial contents while the clean space is small. This allows all problems in and even larger classes to be in catalytic logspace [Buhrman et al, STOC2014]. In [Chmel et al, CCC2026] the catalytic space for reachability was restricted to sublinear space (specifically, space) while remaining in polynomial time. This matches the non-catalytic bounds from [Barnes et al, SICOMP1998]. We extend the reachability bound to shortest distance, proving a simultaneous sublinear catalytic space and polynomial time bound (henceforth called, sublinear ). This is the first simultaneous sublinear space and polynomial time bound for distance even without the catalytic discipline. Moreover, our bound works even for polynomially weighted graphs. Along the way we prove simultaneous near linear catalytic space () and polynomial time bounds for the determinant. We also show some applications to planar matching problems. Our starting point was catalytic computation of reachability in directed graphs by [Cook-Pyne, ITCS2026]. [Edenhofer, arXiv:2602.21088] used it to give a tradeoff between catalytic and non-catalytic space, while [Chmel et al, CCC2026] compress the graph to a smaller graph preserving -reachability to achieve a smaller space bound. All three can be modified to yield an algorithm for unweighted distance. Our contribution is to define an approximation to the walk polynomial in weighted graphs that allows us to infer weighted -distance in sublinear . We do so by non-trivially combining elements from each of the above three papers.
Introduction
Achieving a logspace bound for various problems is the gold standard in space bounded computation – achieved in particular for (undirected) connectivity by Reingold’s breakthrough result [33]. From a reduction to connectivity, this carried over to a plethora of problems like planarity testing [3, 17], bounded treewidth decomposition and MSO evaluation therein [19], planar, bounded genus and bounded treewidth isomorphism [16, 20, 21]. However for problems that were not provably or even believably in Logspace such as reachability, the problem of giving a good deterministic space bounded characterization persisted.
Of course, Savitch’s theorem could squeeze reachability into polylogarithmic space but at the expense of quasipolynomial running time. Rather than compromise on polynomial time, there were attempts to limit the non-determinism by considering unambiguous computation and Reinhardt-Allender [32] were able to prove that Reachability is in fact in unambiguous logspace if only at the expense of non-uniformity. Bourke et al [9] were even able to get rid of the non-uniformity for planar reachability. However non-deterministic computation even if unambiguous is not quite deterministic.
This clarified what was required: a polynomial time, deterministic algorithm that worked in low space. Barnes et al [5] achieved a deterministic sublinear space algorithm for reachability, that was simultaneously polynomial time bounded. Here the matters rested for a long time.
Then in a master stroke, building upon an old idea of Ben-Or & Cleve [6], Buhrman et al [7] introduced the class CL. The idea was to catalyse Logspace with the use of a large filled space that had to be restored to its original contents before the algorithm terminated. Suddenly we were back in the domain of deterministic space computation, more so when Koucký et al. [24] proved that adding non-determinism or randomization to this model does not make it more powerful. In the original paper itself it was shown that not only reachability but a significant part of linear algebra and in fact, all of are in CL.
The one flip side of the great power of the class CL is that it isn’t even known to be polynomially bounded on all inputs i.e. inside P. However Buhrman et al [7] were able to prove a ZPP bound by viewing CL as a probabilistic class which is polynomial time bounded in the expectation.
Soon catalytic logspace was populated with problems that had long defied being classified as deterministically parallelisable – the prominent examples being bipartite matching , linear matroid intersection1 and even general matching [4, 1, 10]. Surprisingly these bound were simultaneously polynomially bounded i.e. in CLP.
Having achieved CLP, a sceptic would tend to believe that this was where the story ended. However, soon enough, contrary to this scepticism the efforts to save catalytic space for CLP problems emerged. A prominent example is the bound on catalytic space simultaneous with logarithmic workspace and polynomial time, for BPL given by Pyne in [31]. Notice that this catalytically achieved the upper bound of proved by Nisan on BPL [30].
A similar bound on reachability would be the natural next step. Preliminary efforts mimicking Pyne [31] were made in Arvind et al [2] using unambiguity to give a tradeoff between space and catalytic space, which was catalytically retracing the footsteps of Reinhardt-Allender [32]. In the deterministic setting, this effort is stymied at the outset by the difficulty in improving the space bound of reachability beyond the Barnes et al [5] bound of slightly sublinear, , along with simultaneous polynomial time even in the non-catalytic setting. Yet, after initial catalytic space versus time tradeoff results by Cook & Pyne [CP26] and space versus catalytic space tradeoff results by Edenhofer [18] the effort culminates in the frontier paper of Chmel et al [11] that achieves the Barnes et al [5] space versus time tradeoff catalytically i.e. works in sublinear catalytic space while simultaneously using logarithmic workspace and polynomial time.
This is where our results enter the fray. We show that not only reachability but also iterated matrix product of matrices each of dimension (this was implicit in [7]), directed distance in vertex graphs and even the determinant of an matrix can be computed in near linear CLP i.e. catalytic logspace using space and simultaneous polynomial time – in fact we show a trade off result between workspace and catalytic space, similar to [18].
We then go on to show that distance in vertex, polynomially bounded edge weighted graphs can be computed in sublinear CLP i.e. catalytic space with simultaneous logarithmic workspace and polynomial time. Even without catalytic space, as far as we are aware this is the first sublinear space bound for weighted distance while staying in polynomial time. Any improvements to this bound on distance would naturally yield corresponding improvements for reachability.
For the determinant result our techniques build on Cook-Pyne [CP26] along with an identity that relates the generating function of elementary symmetric polynomials to the power polynomials along with polynomial interpolation from Hesse et al [22]. For the distance result we build on the frontiers paper Chmel et al [11] and combine it with an tradeoff a la Edenhofer [18].
We also exhibit two matching applications of our results. The first is search and decision for planar perfect matchings in near linear CLP, as a consequence of being able to compute the Pfaffian (analogous to determinant computation) in near linear CLP. The applications combine our main results with techniques from various sources [23, 29, 2]. The second is for the restriction to planar bipartite graphs, we can further improve the decision and search for perfect matching to sub linear CLP which uses a technique from Miller-Naor [27].
Proof Idea
We discuss the essential ideas behind our results.
Tradeoff between space and catalytic space
Cook & Pyne [CP26] give simple catalytic algorithms for directed reachability that not only are time efficient but are catalytic space efficient as well, using roughly quadratic space.2 Their technique (called somewhat picturesquely “stirring the pot” by Nathan Sheffield in an expository essay [She25]) consists of associating a catalytic register with each vertex – these together constitute the “pot”. Now “stirring” this consists of translating the value of each register by the current value of each of its in-neighbours in some arbitrary order several times. Unstirring is the process of stirring the pot in an order reverse of the initial one and restores the original values if done exactly the same number of times as stirring. Their crucial observation is that if the value of the source register is changed initially then after stirring, the value obtained at the destination vertex changes if there is a path from the source vertex to the destination vertex . Thus, stirring followed by saving the value at followed by un stirring followed by changing the value at by 1, stirring again and comparing the stored value at with the new value before unstirring and restoring the value at catalytically reveals the presence of -reachability.
Our first observation is that the stirring technique, applied to a layered version of the original graph, computes a polynomial (if we offset the value at a vertex by times each predecessor’s value) that we call the stirring polynomial and further this is identical with the generating function of walks aka walk polynomial in the original graph.
The stirring technique in [CP26] has been developed by Edenhofer [18] to give a work space vs. catalytic space tradeoff for reachability as well. We mimic their construction to give a similar tradeoff for matrix powering (which is basically a tabulation of walk polynomials) and generalise it to iterated matrix product or equivalently branching program evaluation. This tradeoff yields a near linear catalytic space simulation of the matrix power of while restricting to logarithmic work space and polynomial time3. Our next observation is that this yields determinant of an matrix in near linear CLP using an identity relating the generating function of elementary symmetric polynomials the power polynomials.
On the other hand we show that it also yields a polynomial time and logarithmic space algorithm for powering matrices to small powers, while staying in sublinear catalytic space, 4. Notice that short distances can be computed in these bounds as well since the smallest non-zero exponent in a walk polynomial of a small power will yield that.
Sublinear space algorithms
Next we turn to the recent publication [11] that leverages the techniques in [CP26] to give a sublinear CLP bound for reachability mirroring similar uncatalysed bound from [5] which has not been improved for nearly three decades. [11] construct a sparsified version of the input graph where linear length walks are replaced by sublinear walks preserving reachability where the edges are related to walks of length .
We are able to modify the construction of [11] so that we store distance information on the short-walk-edges. Since we already had (weighted) distance in near linear space this works out to sublinear space when run on the sparsified graph of [11]. This includes being able to compute the weights corresponding to the distances in short walks in sublinear space.
This yields the first sublinear CLP algorithm for distance in a weighted (polynomially bounded) directed graph. In fact, this is true even if we ignore the word catalytic; it remains the first sublinear space algorithm for distance in weighted digraphs which is simultaneously in polynomial time.
Applications
We now turn to some applications of our results concerning matrix powering and distance. We first establish determinant computation in near linear CLP using an identity which relates generating function of elementary symmetric polynomials and power polynomials. In a way similar to the determinant we show Pfaffian computation of a matrix in near linear CLP.
We also show two graph matching applications. The first is the search and decision version of planar perfect matching in near linear CLP. The weighted decision version uses a space efficient version of Kastelyn’s algorithm and Pfaffian computation based on [29]. The search version is handled using a careful application of catalytic isolation [2].
We also show planar bipartite perfect matching in sublinear CLP. For this we use the Miller and Naor algorithm [27], that reduces computation of flows to distances in planar graphs.
Organization
We start with preliminaries in § 2. We establish space-space tradeoff results for matrix powering and branching program in § 3. Using these results we prove weighted distance in sublinear CLP in § 4. In § 5, we give applications concerning determinant and matchings in graphs. Some of the proofs in § 3 to § 5 have been moved to the Appendix.
Preliminaries
Definition 2.1 (Catalytic Computation). A catalytic Turing machine (CTM) M works as follows. The machine consists of three tapes: a read-only input tape, a read-write work tape and a read-write catalytic tape containing some arbitrary string . For some language and input , halts, outputs and the catalytic tape contains .
A language if there exists a CTM which decides membership in and takes time, bits for work tape and bits for catalytic tape.
A language is in Catalytic Logspace, denoted by CL, if the CTM for , for input of size , takes work space and catalytic space.
We denote CLP, sublinear CLP and near-linear CLP as the set of languages which are in CL, their corresponding machines runs in polynomial time and takes catalytic space , and respectively.
Definition 2.2 (Pfaffian). Let be a skew symmetric matrix of even size which is equivalent to an orientation of an undirected graph over vertices. We define perfect matching to be a collection of edges as where .
Since is a skew symmetric matrix, many permutations corresponds to the same perfect matching. Thus, for any perfect matching , the canonical permutation, , is the permutation in which edges are from smaller to larger vertices and edges are listed in increasing order of smaller vertices in each edge, i.e., for , and . We define .
The Pfaffian of (or equivalently ) is defined as
where is the set of all perfect matchings.
Cayley’s theorem states that for a skew symmetric matrix of even size, . This gives us .
Matrix Powering and Branching Programs
In this section we give space-space tradeoff algorithms for matrix powering and branching programs.
Matrix Powering
We first present the space-space tradeoff result for matrix powering.
Theorem 3.1. Given an matrix , and indices , a parameter and a parameter , there is an algorithm running in time , work space and catalytic space , that outputs . In particular, For any , can be computed in
Let be a parameter. We partition the set of vertices, , into parts each of size (assume, for brevity that divides ) as . Each index can be uniquely written as where .
Fix a prime modulus with . The algorithm will use blocks of registers each on the catalytic tape, denoted , and each block will contain registers. Each register stores an element of as in the encoding defined in [18 Appendix A] and so the total catalytic tape is bits.
Consider the register programs for , as described in Algorithm 1.
Algorithm 1 P^\ell_{i,j}(U,V,W_1,\ldots,W_{r=\lceil\log \ell\rceil}) for i,j \in \{0,\ldots,k-1\}
1: Input: A.
2: if \ell = 1 then
3: for u,v \in \mathbb{Z}_n such that r_u = i, r_v = j do
4: V[\lambda_v] = V[\lambda_v] + A[u,v] \cdot U[\lambda_u] (mod q)
5: end for
6: else
7: for m \in \{0,\ldots,k-1\} do
8: P^{\lceil\ell/2\rceil}_{i,m}(U,W_r,W_1,\ldots,W_{r-1}) ▷ Call this step 1
9: P^{\lfloor\ell/2\rfloor}_{m,j}(W_r,V,W_1,\ldots,W_{r-1}) ▷ Step 2
10: (P^{\lceil\ell/2\rceil}_{i,m}(U,W_r,W_1,\ldots,W_{r-1}))^{-1} ▷ Step 3: The inverse of step 1 i.e line 8.
11: end for
12: end if
The programs are reversible. can be obtained by two changes in the above algorithm, replacing “+” with “−” in line 4 and with in line 9.
Fix and . For a vector and an index with , let denote the value added to the register by executing when the input block is initialized so that for every index , .
Claim 3.2. For every and , executing leaves all registers unchanged except those in block .
The proof of the above follows the same as of [18] Claim 3, thus we refer to that for more details.
Claim 3.3 (Matrix powering analogue of [18] Claim 9). Let . For every , , vectors , and every vertex with ,
In particular, if and for all , then
Proof. We proceed by induction on .
Base case . By definition of , for every with ,
Hence,
Inductive step. Assume the statement holds for all lengths strictly smaller than , and let .
Fix . By definition of , the first recursive call produces intermediate contributions stored in corresponding to length- matrix propagation from residue to residue . The second call uses to add contributions corresponding to length- propagation from residue to residue . The third call uncomputes and does not affect .
Let denote the initial contents of . Then
where —notice the dot in the subscript of —denotes a vector in indexed by the block variable . Therefore,
Applying the induction hypothesis to the outer level gives
Applying the induction hypothesis again to the inner term yields
Reordering sums, we get
Using matrix multiplication,
Thus,
completing the proof.
We now give the algorithm for computing and subsequently prove Theorem 3.1.
Algorithm 2 modulo
for do
run
run
end for
return
Proof of Theorem 3.1. For a fixed parameter , and prime , notice that Algorithm 2 computes using catalytic space . Further, observe that the recursion in Algorithm 1 has branching , and recursion depth , thus the time taken is , and workspace used is . Computing for various primes , and applying chinese remaindering in logspace through [22], gives us the desired result.
Branching Program
The space-space tradeoff result for branching program is as follows.
Theorem 3.4 (Catalytic evaluation of branching programs). Let be a layered branching program of length over vertex set , where each layer is described by a transition matrix . Given start state and target state , and a parameter , there is an algorithm computing the weight
in time , work space , and catalytic space .
Algorithm 3 for layered branching programs
Input: layer sequence
if then
for with , do
end for
else
for do
run
run
uncompute
end for
end if
Here, for brevity of notation, we denote for . We remind from the previous discussion that we partition as and each index can be uniquely written as where , .
We again note that the programs are reversible and executing leaves all registers unchanged except those in block , as mentioned in 3.2 and their proofs are analogous.
Claim 3.5 (Branching program analogue of [18] Claim 9). Let be a layered branching program. For all , , vectors , and ,
Proof. We proceed by induction on .
Base case . Immediate from linearity of the transition step:
Inductive step. Let , . By definition of layered branching programs, any length- path decomposes uniquely at layer , giving .
Thus the recursive computation satisfies,
where denotes a vector in indexed by the block variable . Therefore,
Applying the induction hypothesis successively twice to the inner term, we get
Reordering sums,
By matrix multiplication,
Hence,
With the above proved, the proof of Theorem 3.4 follows in the same way as the proof of Theorem 3.1.
Sublinear Catalytic Space for Distances
In this section we prove that distance in polynomially weighted graphs can be computed in sublinear CLP. The main result is stated in the following.
Theorem 4.1. Given an vertex directed graph with polynomially bounded edge weights , and any two designated vertices , we can compute the minimum weight of an - walk in sublinear CLP, assuming there is no negative cycle in the graph.
From Theorem 3.1, we know that we can compute where is an matrix and , in CTISP.
Therefore, we can compute in CTISP (by setting ). Thus we have the following lemma for short length walks:
Lemma 4.2. Given a directed graph on vertices (without self-loops) with polynomially bounded edge weights, we can compute the minimum weight of a walk from to that uses at most edges in sublinear CLP for any constant .
Proof. Let be the weighted adjacency matrix over given by
We can compute in5 sublinear CLP for all . Observe that every monomial appearing in corresponds to an - walk using at most edges, and the degree of the monomial equals the total weight of the walk. Therefore, the least degree appearing in equals the minimum weight of an - walk using at most edges. This least degree monomial can be interpolated in logspace through [22]. Setting proves the claim.
Let be a digraph, and be a multiset. Then for a path of , we say that hits , if . We shall use the following sparsification lemma, which is very similar to [11 Theorem 4.1].
Lemma 4.3. There is an algorithm such that for any directed graph on vertices, a value , and seed for , satisfies:
returns a multiset of size , in logspace
For any set of at most paths each of length , namely of , we have
We push the proof of the above to Appendix A, it is essentially the same as that of [11 Theorem 4.1]. We now prove our main result.
Algorithm 4 DIST
Input: .
Fix , .
for do
is defined by the following loop:
for do
if there is a path from to using at most edges
min weight of a path from to using edges Lemma 4.2
end for
weighted adjacency matrix of with self-loops.
degree of the minimum-degree term in if no such term exists.
end for
return
Proof of Theorem 4.1. We describe the algorithm in Algorithm 4, and discuss the proof of correctness here.
Fix for some constant to be chosen later. Let be fixed, and let , where is as in Lemma 4.3.
Define , and let be a graph on vertex set where iff there is a walk from to in containing at most edges.
Notice that .
Let be a minimum-weight simple path from to . Such a path exists whenever is reachable from , and satisfies . Divide into consecutive segments of edges (except the last which is at most ). Let . For , let denote the segment between vertices and consisting of exactly edges. Let consist of the edges after i.e. – which consists of less than edges. Let . By Lemma 4.3, with probability at least , every segment contains a vertex (for ).
For consecutive vertices , the subpath of between them uses at most edges. Hence . Notice that the number of edges between is at most and the number of edges between is at most . All other pairs are separated by at most edges. is a path in . Assign weights to edges of by , where is the minimum weight of a path from to using at most edges.
The subpath of between any two consecutive vertices among uses at most edges. Hence the corresponding edge of has weight at most the weight of that subpath. Summing over all segments shows that the minimum-weight path from to in has weight at most the minimum-weight path weight in .
Conversely, every edge corresponds to a path in from to of weight exactly . Therefore any path in can be expanded into a walk in of the same total weight from which deleting cycles (necessarily non-negative) yields a path of weight at most the weight of the original compressed path.
It follows that the minimum-weight path from to in has weight at least the minimum-weight path weight in . Hence the minimum-weight path from to in has exactly the same weight as the minimum-weight path from to in .
Let be the weighted adjacency matrix of given by
Using Lemma 4.2, we can compute in sublinear CLP.
We now compute . Let this polynomial be . The least degree appearing in equals the minimum weight of an - path in . Suppose this degree is . If , we set . We enumerate all seeds and return . For at least one good seed, the previous argument shows that equals the minimum weight of an - path in . Therefore is exactly the minimum weight of an - path in . The catalytic space used is
for a sufficiently large choice of . The workspace is clearly , and the running time is polynomial.
Corollary 4.3.1. (Negative cycle detection) Given an -vertex directed graph with polynomially bounded integer edge weights, we can decide whether contains a negative-weight cycle in sublinear CLP.
Proof. We use the same construction as in Theorem 4.1, building for each seed the compressed graph with weights defined as the minimum weight of a - walk using at most edges. But before that if already contained a monomial with a negative exponent then we have detected a negative cycle.
Let be the weighted adjacency matrix:
Consider , i.e., the sum of diagonal entries of .
Observation 4.4. Every monomial in corresponds to a closed walk in of length at most , and the degree of the monomial equals the total weight of the walk.
Claim 4.5. contains a negative-weight cycle iff for some seed , the polynomial contains a monomial of negative degree or contains one such monomial where is the adjacency matrix of the original graph.
Proof. (1) If a negative cycle exists. Let be a negative-weight cycle in . By the same hitting-set argument as in Theorem 4.1, with probability at least , all segments of are represented in , so induces a corresponding closed walk in with total weight upper bounded by that of .
Since has negative weight, repeating it yields closed walks of negative total weight. In particular, within the length bound , there exists a closed walk whose corresponding monomial in has negative degree, since self loops are allowed.
(2) If no negative cycle exists. Then every cycle in has nonnegative weight. Hence every closed walk decomposes into simple cycles of nonnegative total weight, implying every closed walk has nonnegative weight. Therefore all monomials in have nonnegative degree.
Thus no negative-degree monomial appears. Therefore, contains a negative cycle iff for some seed , the polynomial contains a monomial of negative degree or there is a short negative cycle containing at most edges. We enumerate all seeds and accept iff such a negative-degree monomial exists.
The complexity is identical to Theorem 4.1.
Corollary 4.5.1 (Shortest Path). There is an algorithm which, given a positively weighted directed graph , polynomially bounded and vertices , outputs a shortest to path (if it exists) in sublinear CLP.
Proof. We shall in fact show how to find the lexicographically first to shortest path. Suppose the lex-first shortest path is . At the step, we store in the worktape. Now, to find , we enumerate over all out-neighbors of and pick the lex-first such that , and set . To compute , we use Theorem 4.1, and thus we have the desired time-space bound to find the path.
Applications
In this section we give applications related to determinant and matchings in graphs.
Determinant in near linear CLP
We start by giving a space-space tradeoff algorithm for determinant, using Newton’s identities and in fact, using a formula relating the ordinary generating function (OGF) of elementary symmetric polynomials to the power polynomials6. Our starting point is the following well-known identity which we establish in Section B.1 for the sake of completeness.
This brings us to the following.
Theorem 5.1. Let be an matrix over integers. Given , , the value is computable in DLOGTIME-uniform .
Proof. From the given powers we first compute
which is just an iterated sum and hence is in uniform . By eq. (1),
Thus the determinant is the coefficient of in a polynomial of degree over rationals. So we need to plug in distinct values for and do Lagrange interpolation to recover the coefficient of . Consider the rationals that occur in the expression for the polynomial and their denominators (namely for ) and observe that none of the denominators has a prime factor exceeding . Moreover the numerator and denominator of any rational whose sum constitutes a coefficient of is bounded by for some constant . Thus we can do Chinese remaindering with polynomially many primes each of which is polynomially bounded in and greater than precluding it from dividing any denominator. Since the determinant is an integer, the process of Chinese Remaindering modulo the primes will ensure that we obtain the correct determinant. We will use [22] for this, placing it in DLOGTIME-uniform which is contained in , completing the proof.7
Therefore we have the following as corollary.
Corollary 5.1.1. Let be an matrix over integers, and a parameter. Then, can be computed in
Proof. This follows from Theorems 3.1 and 5.1, by combining space-space tradeoff of matrix powering and determinant coefficient-extraction.
Remark 5.2. We note that the determinant can also be shown in near linear CLP using Csanky's algorithm, see [25], or by Berkowitz's method [8].
We now give an analogous space-space tradeoff algorithm for computing Pfaffian by relating it to the determinant.
Pfaffian of a Matrix in near linear CLP
We need the following identity which we prove in Section B.2,
where , for some even integer , and . Here is a fixed skew symmetric integer matrix depending only on , see Section B.2 for more details. Using this notation we have the following.
Theorem 5.3. Let be a skew symmetric matrix over integers. Given , , , , , the value is computable by DLOGTIME-uniform circuits.
Proof. The proof is similar to the proof of Theorem 5.1.
Thus, we get the following as corollary.
Corollary 5.3.1. Let be a skew symmetric matrix over integers, with even, and a parameter. Then, can be computed in
Proof. This follows from Theorems 3.1 and 5.3, by combining space-space tradeoff of matrix powering and Pfaffian coefficient-extraction.
We give one application on matchings which uses the computation of Pfaffian.
Planar Perfect Matching in near linear CLP
Theorem 5.4. Given a planar graph on vertices, and a polynomially bounded weight assignment , we can compute a minimum weight perfect matching of in near linear CLP.
Proof. Notice first that [23, 29] and Corollary 5.3.1 (setting ) immediately give a way to count the number of min-weight perfect matchings of in near linear CLP.
We conclude the proof by the reduction from search to weighted decision as described in [2]. For a self-contained proof see Appendix § 9.
Our second application concerns planar bipartite perfect matching which builds on § 4.
Planar Bipartite Perfect Matching in sublinear CLP
Let be a planar bipartite graph. Miller & Naor [27] (see also [15]) had proved that detecting a perfect matching in an node graph reduces to detecting the absence of a negative cycle in a weighted version of the dual graph. Further, if there is no such negative cycle then shortest distances in the weighted dual yield an explicit representation of a perfect matching. Since the dual graph also has vertices, from Euler’s relation, this yields a sublinear catalytic space algorithm for decision and search for bipartite planar perfect matching. The following is the version of the theorem proved in Appendix § 10.
Theorem 5.5 (Miller & Naor [27]). Given a planar flow network where the image of are in unary, the detection of a feasible flow and its computation can be Logspace reduced to finding the existence of a negative cycle in a planar digraph on vertices with unary integer weights and to distance in a planar digraph on vertices without negative cycles with unary integer weights.
Therefore we get the following.
Theorem 5.6. There is an algorithm that, given a bipartite planar graph on vertices, can find a perfect matching of the graph in sublinear CLP.
Proof. Immediate from Theorem 4.1 and corollary 4.3.1, sublinear weighted distance and negative cycle detection, combined with Theorem 5.5. □
Conclusion
We have shown near linear catalytic log space algorithms for determinant computation, planar matchings, and sublinear catalytic logspace algorithms for distances, and bipartite planar graphs. Couple of interesting questions in these lines are:
Can one design sublinear space algorithms that simultaneously run in polynomial time, catalytic or otherwise, for determinant computation.
Can we have near linear catalytic logspace algorithms for general matchings; note that general matchings have recently been put in CL, [10].
AI disclosure
The Pfaffian identity eq. (2) was discovered through ChatGPT while trying to extend Theorem 5.1 to compute the Pfaffian. We realised that Berkowitz’s method [8] can also be adapted to give a near linear CLP through Chat GPT. Chat GPT Astra was also used for routine formatting and proof verification. The remaining manuscript remains human generated and we take full responsibility for its correctness.
Proof of Lemma 4.3
An undirected graph is an -expander graph if it is a -regular connected graph on vertices, and the second largest eigenvalue (the absolute value) of its normalized adjacency matrix is bounded by ().
Lemma A.1 ([26, 28]). For every prime and every positive integer , there exists an infinite family of expander graphs , such that each is an -expander for and . Furthermore, there is a logspace algorithm (with simultaneous polylogarithmic runtime) that, given, and , computes the neighbor of in .
Definition A.1 (Expander random walk). For any -expander , an expander random walk of length is where is the uniform distribution over , and for every , is the uniform distribution over the -sized neighborhood of the -vertex in the random walk.
Expander random walks of length over behaves similar to uniformly sampling elements from , as follows:
Lemma A.2. Let be an -expander, and let with . Then, for every , the probability that an expander random walk of length in never leaves , is at most .
Lemma A.3 ([Vad12]). For every , there exists a pairwise independent hash function family , where a random function can be sampled from using a seed of bitlength .
Moreover, given any (described by a string in ) and , can be computed in time and space .
Next, we have the following lemma about a pairwise independent hash function family . We say that a hash function hits a set , if intersects . [11] shows that a randomly chosen from , where , hits any -sized subset of with large probability.
Lemma A.4 ([11]). For any constant , let , and let be a pairwise independent hash function family from to . Then, for any of size we have,
Finally, we prove Lemma 4.3.
Proof of Lemma 4.3. For a fixed and small enough to be fixed later, let , , and be an -expander given by Lemma A.1 (assume that is a prime power). Observe that by the choice of and the fact that , we have .
In , is constructed as follows: Use bits to identify a vertex of , this is like uniformly sampling from which is the random variable for a vertex of . Next, sample a -expander random walk using bits to get . This takes bits. since for small enough . Again it can be seen (as in [11]) that for small enough , setting , we have i.e. the seed . Finally, , and thus we have .
Let be the subset of in that contains hash functions in that do not hit . Applying Lemma A.4 for subsets of size , we see that .
Now, using the property of an expander random walks, Lemma A.2 and the fact that , we have
Again, since , the probability that does not intersect with is at most . Applying the union bound over all paths , we have that:
The determinant and Pfaffian as the coefficient of a polynomial
Determinant
Newton’s identities give us a way to compute elementary symmetric polynomials from power sums and vice-versa. Let be variables, denote for by the -th power sum:
and for denote by the elementary symmetric polynomial, that is, the sum of all distinct products of distinct variables, so
Let be the eigenvalues of the matrix . We know that sum of eigenvalues of a matrix is equal to its trace and eigenvalues of are the eigenvalues of raised to the power , for more details refer to any standard linear algebra textbook.
Then from the above two facts, we get , which we can compute using the matrix powering algorithm from 3.1. Thus , for , are our power sums and from these we will compute the th elementary symmetric polynomial , which is equal to the determinant of the matrix .
The ordinary generating function of the elementary symmetric polynomials is
Taking logarithms as formal power series gives (see Stanley [Sta99, Chapter 7, Equation (7.23)])
Hence we have,
Since has degree at most , the coefficient of is obtained from the truncation modulo , thus yielding eq. (1).
Pfaffian
Fix the matrix:
and be a block diagonal matrix of size as . We have , and .
Consider , which is valid since the matrix is skew symmetric too. Every term in a Pfaffian is a product of matrix entries. Therefore has degree at most , and choosing the contribution from every factor gives .
By Cayley’s theorem . Set . Then we have
Since , it is the unique formal square root with constant term 1, thus we have
From the determinant identity we derived in the previous section, we get
and consequently we get eq. (2).
Remaining part of Proof of Theorem 5.4
Theorem 5.4. Given a planar graph on vertices, and a polynomially bounded weight assignment , we can compute a minimum weight perfect matching of in near linear CLP.
Proof. Now, consider an extra block of catalytic space consisting of bits. A compress or compute algorithm to compute a min-weight perfect matching is as follows (this is a careful adaptation of [2]’s reduction from weighted decision to weighted search):
Let be the amount of free space available to us from the catalytic tape.
Read the first bits after number of bits on the catalytic tape, as a weight assignment: , . Check if the weight assignment min-isolates a perfect matching in (use the counting oracle to do this, done in [2]), where is a large constant.
Suppose is indeed a min-isolating weight assignment. Then output the unique min-weight matching w.r.t , as the set of edges on deleting which the minimum value changes (done in detail in [2]) and go to step 5 for reconstructing the catalytic tape.
Suppose is not isolating, then we find a threshold edge (use [2]), and replace with where is currently the number of free bits available (which is ), and is just -many bits available to us for any computation. At this stage, either or not. If , repeat from step 2. Otherwise do the following: Using the oracle for weighted counting as a decision oracle, search for a min-weight perfect matching using self-reducibility of matching. Clearly, self-reduction requires to store edges, i.e. uses at most space. This can be done in the . Finally go to step 5 to reconstruct the catalytic tape.
To reconstruct the catalytic tape, we decompress the weight assignments backwards, i.e, consider the first -bits after the ( number of bits): . Compute the weight of the threshold edge ([2]), and replace it with and subtract . Repeat this process, until , i.e. when the catalytic tape has finally been restored.
To fill in the details, we refer [2]. The above clearly requires catalytic space, and runs in polynomial time. Thus, we have the result. ∩ევნ
An overview of Miller & Naor in our context
We now make the sketch from § 5.4 more precise. Miller & Naor [27] deal more generally with the problem of finding a feasible flow in a capacitated planar network with designated demands for every vertex. In the case of planar bipartite matching, every vertex in one bipartition has a negative demand of (i.e. a surplus of 1) and every vertex in the other bipartition a positive demand of . On the other hand every arc has capacity while the reverse arc has a capacity , .
In order to construct such a flow function , they first ignore the capacities and find a flow in the network satisfying the demands. To do so, they construct a spanning tree in the network and make sure that every edge carries a flow equal to the sum of the demands in the subtree containing formed by deleting the edge from the tree. Notice that the tacit assumption is that the total demand in the network is zero and hence the flow on the edge matches the surplus on the side subtree of . It also means is skew-symmetric.
They then construct a new flow network with the capacity of edge being (and for the reverse edge , ). They go on to construct the directed dual of this network where the dual of the edge is obtained by turning the edge , clockwise. The weight . They show that the original flow network has a valid flow iff the dual flow network under the weights has no negative cycle.
If the dual does not have a negative cycle, shortest paths are well defined in the dual. Let be an arbitrary vertex in the dual (i.e. a face in the primal). Compute the shortest distance from to every vertex . Define where is the directed dual edge of . Then, [27] show that is a valid flow in the residual graph i.e. is skew-symmetric and for every edge . In other words, is a valid flow in the original network . This is because it is skew-symmetric from the skew-symmetry of , and satisfies .
Therefore in conclusion we obtain Theorem 5.5.
References
- [1]Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear matroid intersection is in catalytic logspace. In 17th Innovations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026, pages 3:1–3:23, 2026.arxiv.org/abs/2509.06435
- [2]V. Arvind, Srijan Chakraborty, and Samir Datta. Derandomizing isolation in catalytic logspace. 2026.arxiv.org/abs/2512.09374
- [3]Eric Allender and Meena Mahajan. The complexity of planarity testing. Inf. Comput., 189(1):117–134, 2004.
- [4]Aryan Agarwala and Ian Mertz. Bipartite matching is in catalytic logspace. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 360–372. IEEE, 2025.arxiv.org/abs/2504.09991
- [5]Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM Journal on Computing, 27(5):1273–1282, 1998.
- [6]Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54–58, 1992.
- [7]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 857–866. ACM, 2014.
- [8]Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett., 18(3):147–150, 1984.DOI
- [9]Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Trans. Comput. Theory, 1(1):1–17, 2009.
- [10]Srijan Chakraborty, Samir Datta, Aryan Kusre, Partha Mukhopadhyay, and Amit Sinhababu. Maximum matching and related problems in catalytic logspace, 2026.arxiv.org/abs/2604.24275
- [11]Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, and Ninad Rajgopal. Frontier Space-Time Algorithms Using Only Full Memory. In Dana Moshkovitz, editor, 41st Computational Complexity Conference (CCC 2026), volume 383 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:23, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
- [12]Andrew Chiu, George I. Davida, and Bruce E. Litow. Division in logspace-uniform NC¹. RAIRO Theor. Informatics Appl., 35(3):259–275, 2001.
- [13]Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Thomas Thierauf. Bipartite matching is in NC. Electron. Colloquium Comput. Complex., TR26, 2026.
- [15]Samir Datta, Arjun Gopalan, Raghav Kulkarni, and Raghunath Tewari. Improved bounds for bipartite matching on surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, February 29 - March 3, 2012, pages 254–265, 2012.DOI
- [16]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. ACM Trans. Comput. Theory, 14(2):8:1–8:33, 2022.
- [17]Samir Datta and Gautam Prakriya. Planarity testing revisited. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings, pages 540–551, 2011.
- [18]Roman Edenhofer. A space-space trade-off for directed st-connectivity. 2026.arxiv.org/abs/2602.21088
- [19]Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of bodlaender and courcelle. In FOCS, pages 143–152, 2010.DOI
- [20]Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 383–392. ACM, 2014.DOI
- [21]Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. ACM Trans. Comput. Theory, 9(3):12:1–12:29, 2017.
- [22]William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695–716, 2002. Special Issue on Complexity 2001.DOI
- [23]P W Kastelyn. Graph theory and crystal physics. In F Harary, editor, Graph Theory and Theoretical Physics, pages 43–110. Academic Press, 1967.
- [24]Michal Koucký, Ian Mertz, Edward Pyne, and Sasha Sami. Collapsing catalytic classes. CoRR, abs/2504.08444, 2025.arxiv.org/abs/2504.08444
- [25]Dexter C. Kozen. Csanky’s Algorithm, pages 166–170. Springer New York, New York, NY, 1992.DOI
- [26]Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.
- [27]Gary L. Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. SIAM J. Comput., 24(5):1002–1017, 1995.
- [28]Moshe Morgenstern. Existence and explicit constructions of q+1-regular ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B, 62(1):44–62, 1994.DOI
- [29]Meena Mahajan, P. R. Subramanya, and V. Vinay. The combinatorial approach yields an nc algorithm for computing pfaffians. Discret. Appl. Math., 143(1-3):1–16, 2004.DOI
- [30]Noam Nisan. RL ⊆ = SC. Comput. Complex., 4:1–11, 1994.
- [31]Edward Pyne. Derandomizing logspace with a small shared hard drive. In Rahul Santhanam, editor, 39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA, volume 300 of LIPIcs, pages 4:1–4:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.DOI
- [32]Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM Journal of Computing, 29:1118–1131, 2000. An earlier version appeared in FOCS 1997, pp. 244–253.
- [33]Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), September 2008.DOI