betaFeedback

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 NL\mathsf{NL} and even larger classes to be in catalytic logspace [Buhrman et al, STOC2014]. In [Chmel et al, CCC2026] the catalytic space for reachability was restricted to sublinear space (specifically, n/2θ(log⁡n)n \big/ 2^{θ(\sqrt{\log n})} space) while remaining in polynomial time. This matches the non-catalytic bounds from [Barnes et al, SICOMP1998]. We extend the reachability bound to shortest distance, proving a simultaneous sublinear catalytic space and polynomial time bound (henceforth called, sublinear CLP\mathsf{CLP}). This is the first simultaneous sublinear space and polynomial time bound for distance even without the catalytic discipline. Moreover, our bound works even for polynomially weighted graphs. Along the way we prove simultaneous near linear catalytic space (O(nlog⁡O(1)n)\mathcal{O}(n\log^{O(1)}{n})) and polynomial time bounds for the determinant. We also show some applications to planar matching problems. Our starting point was catalytic computation of reachability in directed graphs by [Cook-Pyne, ITCS2026]. [Edenhofer, arXiv:2602.21088] used it to give a tradeoff between catalytic and non-catalytic space, while [Chmel et al, CCC2026] compress the graph to a smaller graph preserving s,ts,t-reachability to achieve a smaller space bound. All three can be modified to yield an algorithm for unweighted distance. Our contribution is to define an approximation to the walk polynomial in weighted graphs that allows us to infer weighted s,ts,t-distance in sublinear CLP\mathsf{CLP}. 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 TC1\mathrm{TC}^{1} 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 O(log⁡2n)O(\log^{2} n) 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 SC2\mathrm{SC}^{2} 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, n2Θ(log⁡n)\frac{n}{2^{\Theta(\sqrt{\log n})}}, 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 nn matrices each of dimension nn (this was implicit in [7]), directed distance in nn vertex graphs and even the determinant of an n×nn \times n matrix can be computed in near linear CLP i.e. catalytic logspace using O(nlog⁡O(1)n)O(n \log^{O(1)} n) 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 nn vertex, polynomially bounded edge weighted graphs can be computed in sublinear CLP i.e. n2log⁡n\frac{n}{2^{\sqrt{\log n}}} 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 IMMn\mathrm{IMM}_n 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 ss to the destination vertex tt. Thus, stirring followed by saving the value at tt followed by un stirring followed by changing the value at ss by 1, stirring again and comparing the stored value at tt with the new value before unstirring and restoring the value at ss catalytically reveals the presence of s,ts,t-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 xx 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 nn while restricting to logarithmic work space and polynomial time3. Our next observation is that this yields determinant of an n×nn \times n 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, 2Θ(log⁡n)2^{\Theta(\sqrt{\log n})} while staying in sublinear catalytic space, O(n2Θ(log⁡n))O\left(\frac{n}{2^{\Theta(\sqrt{\log n})}}\right)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 2Θ(log⁡n)2^{\Theta(\sqrt{\log n})}.

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 MM consists of three tapes: a read-only input tape, a read-write work tape and a read-write catalytic tape containing some arbitrary string τ\tau. For some language LL and input xx, MM halts, outputs x∈Lx \in L and the catalytic tape contains τ\tau.

A language L∈CTISP[t,w,c]L \in\mathrm{CTISP}[t,w,c] if there exists a CTM which decides membership in LL and takes tt time, ww bits for work tape and cc bits for catalytic tape.

A language LL is in Catalytic Logspace, denoted by CL, if the CTM for LL, for input of size nn, takes O(log⁡n)O(\log n) work space and O(nO(1))O(n^{O(1)}) 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 nO(1)n^{O(1)}, n2Θ(log⁡n)\frac{n}{2^{\Theta(\sqrt{\log n})}} and nlog⁡O(1)nn\log^{O(1)} n respectively.

Definition 2.2 (Pfaffian). Let AA be a skew symmetric matrix of even size n×nn \times n which is equivalent to an orientation of an undirected graph GG over nn vertices. We define perfect matching MM to be a collection of edges as M={(σ(1),σ(2)),(σ(3),σ(4))…,(σ(n−1),σ(n))}M = \{(\sigma(1),\sigma(2)),(\sigma(3),\sigma(4))\ldots,(\sigma(n-1),\sigma(n))\} where σ∈Sn\sigma\in S_n.

Since AA is a skew symmetric matrix, many permutations corresponds to the same perfect matching. Thus, for any perfect matching MM, the canonical permutation, σM\sigma_M, 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., σM(2i−1)<σM(2i)\sigma_M(2i-1) < \sigma_M(2i) for i=1,2,…,n/2i = 1,2,\ldots,n/2, and σM(1)<σM(3)<⋯<σM(n−1)\sigma_M(1) < \sigma_M(3) < \cdots< \sigma_M(n-1). We define wt⁡(σM)=∏i=1n/2A[σM(2i−1),σM(2i)]\operatorname{wt}(\sigma_M) = \prod_{i=1}^{n/2} A[\sigma_M(2i-1),\sigma_M(2i)].

The Pfaffian of AA (or equivalently GG) is defined as

Pf⁡(A)=∑M∈Msgn⁡(σM)wt⁡(σM),\operatorname{Pf}(A) = \sum_{M \in\mathcal{M}} \operatorname{sgn}(\sigma_M)\operatorname{wt}(\sigma_M),

where M\mathcal{M} is the set of all perfect matchings.

Cayley’s theorem states that for a skew symmetric matrix AA of even size, det⁡(A)=(Pf⁡(A))2\det(A) = (\operatorname{Pf}(A))^2. This gives us ∣Pf⁡(A)∣=(det⁡(A))12|\operatorname{Pf}(A)| = (\det(A))^{\frac{1}{2}}.

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 n×nn \times n matrix AA, and indices s,t∈Zns,t \in\mathbb{Z}_n, a parameter ℓ∈N+\ell\in\mathbb{N}^{+} and a parameter k∈[1,n]k \in[1,n], there is an algorithm running in time poly⁡(n,(3k)log⁡ℓ)\operatorname{poly}(n,(3k)^{\log\ell}), work space O(log⁡ℓ⋅log⁡(3k)+log⁡n)O(\log\ell\cdot\log(3k) + \log n) and catalytic space O(nk⋅log⁡n⋅log⁡ℓ)O\left(\frac{n}{k} \cdot\log n \cdot\log\ell\right), that outputs Aℓ[s,t]A^{\ell}[s,t]. In particular, For any k∈[1,n]k \in[1,n], Aℓ[s,t]A^{\ell}[s,t] can be computed in

CTISP⁡[poly⁡(n,(3k)log⁡ℓ),O(log⁡ℓ⋅log⁡(3k)+log⁡n),O(nk⋅log⁡n⋅log⁡ℓ)].\operatorname{CTISP}\left[\operatorname{poly}(n,(3k)^{\log\ell}), O(\log\ell\cdot\log(3k) + \log n), O\left(\frac{n}{k} \cdot\log n \cdot\log\ell\right)\right].

Let k∈[1,n]k \in[1,n] be a parameter. We partition the set of vertices, Zn\mathbb{Z}_n, into kk parts each of size n/kn/k (assume, for brevity that kk divides nn) as Zn=⨆i∈Zk{v∈Zn:v≡i(modk)}\mathbb{Z}_n = \bigsqcup_{i \in\mathbb{Z}_k}\{v \in\mathbb{Z}_n : v \equiv i \pmod{k}\}. Each index vv can be uniquely written as λvk+rv\lambda_v k + r_v where λv=⌊v/k⌋,rv∈Zk\lambda_v = \lfloor v/k \rfloor, r_v \in\mathbb{Z}_k.

Fix a prime modulus qq with log⁡q=O(log⁡n)\log q = O(\log n). The algorithm will use ⌈log⁡ℓ⌉+2\lceil\log\ell\rceil+ 2 blocks of registers each on the catalytic tape, denoted U,V,W1,…,Wr=⌈log⁡ℓ⌉U,V,W_1,\ldots,W_{r=\lceil\log\ell\rceil}, and each block will contain n/kn/k registers. Each register stores an element of Zq\mathbb{Z}_q as in the encoding defined in [18 Appendix A] and so the total catalytic tape is O((n/k)log⁡nlog⁡ℓ)O((n/k)\log n\log\ell) bits.

Consider the register programs Pi,jℓP^\ell_{i,j} for ℓ∈N+,i,j∈{0,…,k−1}\ell\in\mathbb{N}^{+}, i,j \in\{0,\ldots,k-1\}, 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 Pi,jℓP^\ell_{i,j} are reversible. (Pi,jℓ)−1(P^\ell_{i,j})^{-1} can be obtained by two changes in the above algorithm, replacing “+” with “−” in line 4 and Pm,j⌊ℓ/2⌋P^{\lfloor\ell/2\rfloor}_{m,j} with (Pm,j⌊ℓ/2⌋)−1(P^{\lfloor\ell/2\rfloor}_{m,j})^{-1} in line 9.

Fix ℓ∈N+\ell\in\mathbb{N}^{+} and i,j∈{0,…,k−1}i,j \in\{0,\ldots,k-1\}. For a vector τ=(τ0,…,τ(n/k)−1)∈Zqn/k\tau=(\tau_0,\ldots,\tau_{(n/k)-1}) \in\mathbb{Z}_q^{n/k} and an index v∈Znv \in\mathbb{Z}_n with v≡j(modk)v \equiv j \pmod{k}, let αℓ,v(i,j)(τ)∈Zq\alpha^{(i,j)}_{\ell,v}(\tau) \in\mathbb{Z}_q denote the value added to the register V[λv]V[\lambda_v] by executing Pi,jℓ(U,V,W1,…,Wr)P^\ell_{i,j}(U,V,W_1,\ldots,W_r) when the input block UU is initialized so that for every index u≡i(modk)u \equiv i \pmod{k}, U[λu]=τλuU[\lambda_u]=\tau_{\lambda_u}.

Claim 3.2. For every ℓ∈N+\ell\in\mathbb{N}^{+} and i,j∈{0,…,k−1}i,j \in\{0,\ldots,k-1\}, executing Pi,jℓ(U,V,W1,…,Wr)P^\ell_{i,j}(U,V,W_1,\ldots,W_r) leaves all registers unchanged except those in block VV.

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 A∈Zqn×nA \in\mathbb{Z}_q^{n \times n}. For every ℓ∈N+\ell\in\mathbb{N}^{+}, i,j∈{0,…,k−1}i,j \in\{0,\ldots,k-1\}, vectors τ,b∈Zqn/k\tau,b \in\mathbb{Z}_q^{n/k}, and every vertex v∈Znv \in\mathbb{Z}_n with v≡j(modk)v \equiv j \pmod{k},

αℓ,v(i,j)(τ+b)−αℓ,v(i,j)(τ)≡∑u∈Zn:u≡i(modk)bλu(Aℓ)u,v(modq).\alpha_{\ell,v}^{(i,j)}(\tau+b)-\alpha_{\ell,v}^{(i,j)}(\tau)\equiv\sum_{\substack{u\in\mathbb{Z}_n:\\u\equiv i\;(\mathop{\mathrm{mod}} k)}}b_{\lambda_u}(A^\ell)_{u,v}\pmod q.

In particular, if bλs=1b_{\lambda_s}=1 and bλ=0b_\lambda=0 for all λ≠λs\lambda\ne\lambda_s, then

αℓ,v(i=rs,j)(τ+b)−αℓ,v(i=rs,j)(τ)≡(Aℓ)s,v(modq).\alpha_{\ell,v}^{(i=r_s,j)}(\tau+b)-\alpha_{\ell,v}^{(i=r_s,j)}(\tau)\equiv(A^\ell)_{s,v}\pmod q.

Proof. We proceed by induction on ℓ\ell.

Base case ℓ=1\ell=1. By definition of Pi,j1P_{i,j}^{1}, for every vv with rv=jr_v=j,

α1,v(i,j)(τ)=∑u∈Zn:ru=iA[u,v]⋅τλu.\alpha_{1,v}^{(i,j)}(\tau)=\sum_{\substack{u\in\mathbb{Z}_n:\\r_u=i}}A[u,v]\cdot\tau_{\lambda_u}.

Hence,

α1,v(i,j)(τ+b)−α1,v(i,j)(τ)=∑u∈Znru=ibλuA[u,v].\alpha_{1,v}^{(i,j)}(\tau+b)-\alpha_{1,v}^{(i,j)}(\tau)=\sum_{\substack{u\in\mathbb{Z}_n\\r_u=i}}b_{\lambda_u}A[u,v].

Inductive step. Assume the statement holds for all lengths strictly smaller than ℓ≥2\ell\ge2, and let r=⌈log⁡ℓ⌉r=\lceil\log\ell\rceil.

Fix m∈{0,…,k−1}m\in\{0,\ldots,k-1\}. By definition of Pi,jℓP_{i,j}^{\ell}, the first recursive call Pi,m⌈ℓ/2⌉(U,Wr,W1,…,Wr−1)P_{i,m}^{\lceil\ell/2\rceil}(U,W_r,W_1,\ldots,W_{r-1}) produces intermediate contributions stored in WrW_r corresponding to length-⌈ℓ/2⌉\lceil\ell/2\rceil matrix propagation from residue ii to residue mm. The second call Pm,j⌊ℓ/2⌋(Wr,V,W1,…,Wr−1)P_{m,j}^{\lfloor\ell/2\rfloor}(W_r,V,W_1,\ldots,W_{r-1}) uses WrW_r to add contributions corresponding to length-⌊ℓ/2⌋\lfloor\ell/2\rfloor propagation from residue mm to residue jj. The third call uncomputes WrW_r and does not affect VV.

Let σ∈Zqn/k\sigma\in\mathbb{Z}_q^{n/k} denote the initial contents of WrW_r. Then

αℓ,v(i,j)(τ)≡∑m∈Zkα⌊ℓ/2⌋,v(m,j)(σ+α⌈ℓ/2⌉,⋅(i,m)(τ))(modq).\alpha_{\ell,v}^{(i,j)}(\tau)\equiv\sum_{m\in\mathbb{Z}_k}\alpha_{\lfloor\ell/2\rfloor,v}^{(m,j)}\left(\sigma+\alpha_{\lceil\ell/2\rceil,\cdot}^{(i,m)}(\tau)\right)\pmod q.

where α⌈ℓ/2⌉,⋅(i,m)(τ)\alpha_{\lceil\ell/2\rceil,\cdot}^{(i,m)}(\tau)—notice the dot in the subscript of α⌈ℓ/2⌉,⋅(i,m)(τ)\alpha_{\lceil\ell/2\rceil,\cdot}^{(i,m)}(\tau)—denotes a vector in Zqn/k\mathbb{Z}_q^{n/k} indexed by the block variable λu∈[n/k]\lambda_u\in[n/k]. Therefore,

αℓ,v(i,j)(τ+b)−αℓ,v(i,j)(τ)≡∑m∈Zk(α⌊ℓ/2⌋,v(m,j)(σ+α⌈ℓ/2⌉,⋅(i,m)(τ+b))−α⌊ℓ/2⌋,v(m,j)(σ+α⌈ℓ/2⌉,⋅(i,m)(τ)))(modq).\alpha_{\ell,v}^{(i,j)}(\tau+b)-\alpha_{\ell,v}^{(i,j)}(\tau)\equiv\sum_{m\in\mathbb{Z}_k}\left(\alpha_{\lfloor\ell/2\rfloor,v}^{(m,j)}\left(\sigma+\alpha_{\lceil\ell/2\rceil,\cdot}^{(i,m)}(\tau+b)\right)-\alpha_{\lfloor\ell/2\rfloor,v}^{(m,j)}\left(\sigma+\alpha_{\lceil\ell/2\rceil,\cdot}^{(i,m)}(\tau)\right)\right)\pmod q.

Applying the induction hypothesis to the outer level gives

≡∑m∈Zk∑u∈Zn:ru=m(α⌈ℓ/2⌉,u(i,m)(τ+b)−α⌈ℓ/2⌉,u(i,m)(τ))(A⌊ℓ/2⌋)u,v(modq).\equiv\sum_{m\in\mathbb{Z}_k}\sum_{\substack{u\in\mathbb{Z}_n:\\r_u=m}}\left(\alpha_{\lceil\ell/2\rceil,u}^{(i,m)}(\tau+b)-\alpha_{\lceil\ell/2\rceil,u}^{(i,m)}(\tau)\right)(A^{\lfloor\ell/2\rfloor})_{u,v}\pmod q.

Applying the induction hypothesis again to the inner term yields

≡∑m∈Zk∑u∈Zn:ru=m∑w∈Zn:rw=ibλw(A⌈ℓ/2⌉)w,u(A⌊ℓ/2⌋)u,v(modq).\equiv\sum_{m\in\mathbb{Z}_k}\sum_{\substack{u\in\mathbb{Z}_n:\\r_u=m}}\sum_{\substack{w\in\mathbb{Z}_n:\\r_w=i}}b_{\lambda_w}(A^{\lceil\ell/2\rceil})_{w,u}(A^{\lfloor\ell/2\rfloor})_{u,v}\pmod q.

Reordering sums, we get

≡∑w∈Zn:rw=ibλw∑u∈Zn(A⌈ℓ/2⌉)w,u(A⌊ℓ/2⌋)u,v(modq).\equiv\sum_{\substack{w\in\mathbb{Z}_n:\\ r_w=i}} b_{\lambda_w}\sum_{u\in\mathbb{Z}_n}(A^{\lceil\ell/2\rceil})_{w,u}(A^{\lfloor\ell/2\rfloor})_{u,v}\pmod q.

Using matrix multiplication,

∑u∈Zn(A⌈ℓ/2⌉)w,u(A⌊ℓ/2⌋)u,v=(Aℓ)w,v.\sum_{u\in\mathbb{Z}_n}(A^{\lceil\ell/2\rceil})_{w,u}(A^{\lfloor\ell/2\rfloor})_{u,v}=(A^\ell)_{w,v}.

Thus,

αℓ,v(i,j)(τ+b)−αℓ,v(i,j)(τ)≡∑w∈Zn:rw=ibλw(Aℓ)w,v(modq),\alpha_{\ell,v}^{(i,j)}(\tau+b)-\alpha_{\ell,v}^{(i,j)}(\tau)\equiv\sum_{\substack{w\in\mathbb{Z}_n:\\ r_w=i}}b_{\lambda_w}(A^\ell)_{w,v}\pmod q,

completing the proof.

We now give the algorithm for computing Aℓ[s,t]A^\ell[s,t] and subsequently prove Theorem 3.1.

Algorithm 2 Aℓ[s,t]A^\ell[s,t] modulo qq

  1. for c∈{0,1}c\in\{0,1\} do

  2. U[λs]←U[λs]+cU[\lambda_s]\leftarrow U[\lambda_s]+c

  3. run Prs,rtℓ(U,V,W1,…,Wr)P^\ell_{r_s,r_t}(U,V,W_1,\ldots,W_r)

  4. αc←V[λt]\alpha_c\leftarrow V[\lambda_t]

  5. run Prs,rtℓ(U,V,W1,…,Wr)−1P^\ell_{r_s,r_t}(U,V,W_1,\ldots,W_r)^{-1}

  6. U[λs]←U[λs]−cU[\lambda_s]\leftarrow U[\lambda_s]-c

  7. end for

  8. return α1−α0(modq)\alpha_1-\alpha_0\pmod q

Proof of Theorem 3.1. For a fixed parameter kk, and prime qq, notice that Algorithm 2 computes Aℓ[s,t](modq)A^\ell[s,t]\pmod q using catalytic space (n/k)log⁡ℓlog⁡q=O((n/k)log⁡ℓlog⁡n)(n/k)\log\ell\log q=O((n/k)\log\ell\log n). Further, observe that the recursion in Algorithm 1 has branching kk, and recursion depth log⁡ℓ\log\ell, thus the time taken is poly⁡(n,(3k)log⁡ℓ)\operatorname{poly}(n,(3k)^{\log\ell}), and workspace used is O(log⁡n+log⁡ℓlog⁡(3k))O(\log n+\log\ell\log(3k)). Computing Aℓ[s,t](modq)A^\ell[s,t]\pmod q for various primes qq, 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 GG be a layered branching program of length ℓ\ell over vertex set Zn\mathbb{Z}_n, where each layer ℓi∈{1,…,ℓ}\ell_i\in\{1,\ldots,\ell\} is described by a transition matrix A(ℓi)∈Zqn×nA^{(\ell_i)}\in\mathbb{Z}_q^{n\times n}. Given start state ss and target state tt, and a parameter k∈[1,n]k\in[1,n], there is an algorithm computing the weight

∑π:s⇝t∏r=1ℓAπr−1,πr(r)=(A(1)A(2)⋯A(ℓ))[s,t]\sum_{\pi:s\leadsto t}\prod_{r=1}^{\ell}A^{(r)}_{\pi_{r-1},\pi_r}=\left(A^{(1)}A^{(2)}\cdots A^{(\ell)}\right)[s,t]

in time poly⁡(n,(3k)log⁡ℓ)\operatorname{poly}(n,(3k)^{\log\ell}), work space O(log⁡n+log⁡(3k)⋅log⁡ℓ)O(\log n+\log(3k)\cdot\log\ell), and catalytic space O(nklog⁡nlog⁡ℓ)O\left(\frac{n}{k}\log n\log\ell\right).

Algorithm 3 Pi,jℓ(U,V,W1,…,Wr)[A(1..ℓ)]P^{\ell}_{i,j}(U,V,W_1,\ldots,W_r)[A^{(1..\ell)}] for layered branching programs

  1. Input: layer sequence A(1),…,A(ℓ)A^{(1)},\ldots,A^{(\ell)}

  2. if ℓ=1\ell=1 then

  3. &nbsp;&nbsp;&nbsp;&nbsp;for u,v∈Znu,v\in\mathbb{Z}_n with ru=ir_u=i, rv=jr_v=j do

  4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;V[λv]←V[λv]+A(1)[u,v]⋅U[λu](modq)V[\lambda_v]\leftarrow V[\lambda_v]+A^{(1)}[u,v]\cdot U[\lambda_u]\pmod q

  5. &nbsp;&nbsp;&nbsp;&nbsp;end for

  6. else

  7. &nbsp;&nbsp;&nbsp;&nbsp;for m∈Zkm\in\mathbb{Z}_k do

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;run Pi,m⌈ℓ/2⌉(U,Wr,W1,…,Wr−1)[A(1..ℓ1)]P^{\lceil\ell/2\rceil}_{i,m}(U,W_r,W_1,\ldots,W_{r-1})[A^{(1..\ell_1)}] ▹ℓ1=⌈ℓ/2⌉\triangleright\ell_1=\lceil\ell/2\rceil

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;run Pm,j⌊ℓ/2⌋(Wr,V,W1,…,Wr−1)[A(ℓ1+1..ℓ)]P^{\lfloor\ell/2\rfloor}_{m,j}(W_r,V,W_1,\ldots,W_{r-1})[A^{(\ell_1+1..\ell)}]

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;uncompute WrW_r

  11. &nbsp;&nbsp;&nbsp;&nbsp;end for

  12. end if

Here, for brevity of notation, we denote A(i..j)=A(i)⋯A(j)A^{(i..j)}=A^{(i)}\cdots A^{(j)} for i<ji<j. We remind from the previous discussion that we partition [0,n−1][0,n-1] as [0,n−1]=⨆i∈Zk{v∈[0,n−1]:v≡i(modk)}[0,n-1]=\bigsqcup_{i\in\mathbb{Z}_k}\{v\in[0,n-1]:v\equiv i\pmod k\} and each index vv can be uniquely written as λvk+rv\lambda_v k+r_v where λv=⌊v/k⌋\lambda_v=\lfloor v/k\rfloor, rv∈Zkr_v\in\mathbb{Z}_k.

We again note that the programs Pi,jℓP^{\ell}_{i,j} are reversible and executing Pi,jℓ(U,V,W1,…,Wr)P^{\ell}_{i,j}(U,V,W_1,\ldots,W_r) leaves all registers unchanged except those in block VV, as mentioned in 3.2 and their proofs are analogous.

Claim 3.5 (Branching program analogue of [18] Claim 9). Let A(1),…,A(ℓ)A^{(1)},\ldots,A^{(\ell)} be a layered branching program. For all ℓ≥1\ell\geq1, i,j∈{0,…,k−1}i,j\in\{0,\ldots,k-1\}, vectors τ,b∈Zqn/k\tau,b\in\mathbb{Z}_q^{n/k}, and v≡j(modk)v\equiv j\pmod k,

αℓ,v(i,j)(τ+b)−αℓ,v(i,j)(τ)≡∑u∈Znru=ibλu⋅(A(1)A(2)⋯A(ℓ))u,v(modq).\alpha^{(i,j)}_{\ell,v}(\tau+b)-\alpha^{(i,j)}_{\ell,v}(\tau)\equiv\sum_{\substack{u\in\mathbb{Z}_n\\r_u=i}}b_{\lambda_u}\cdot\left(A^{(1)}A^{(2)}\cdots A^{(\ell)}\right)_{u,v}\pmod q.

Proof. We proceed by induction on ℓ\ell.

Base case ℓ=1\ell=1. Immediate from linearity of the transition step:

α1,v(i,j)(τ)≡∑u∈Znru=iA(1)[u,v]⋅τλu(modq).\alpha^{(i,j)}_{1,v}(\tau)\equiv\sum_{\substack{u\in\mathbb{Z}_n\\r_u=i}}A^{(1)}[u,v]\cdot\tau_{\lambda_u}\pmod q.

Inductive step. Let ℓ1=⌈ℓ/2⌉\ell_1=\lceil\ell/2\rceil, ℓ2=⌊ℓ/2⌋\ell_2=\lfloor\ell/2\rfloor. By definition of layered branching programs, any length-ℓ\ell path decomposes uniquely at layer ℓ1\ell_1, giving A(1..ℓ)=A(1..ℓ1)⋅A(ℓ1+1..ℓ)A^{(1..\ell)}=A^{(1..\ell_1)}\cdot A^{(\ell_1+1..\ell)}.

Thus the recursive computation satisfies,

αℓ,v(i,j)(τ)≡∑m∈Zkαℓ2,v(m,j)(σ+αℓ1,⋅(i,m)(τ))(modq),\alpha^{(i,j)}_{\ell,v}(\tau)\equiv\sum_{m\in\mathbb{Z}_k}\alpha^{(m,j)}_{\ell_2,v}\left(\sigma+\alpha^{(i,m)}_{\ell_1,\cdot}(\tau)\right)\pmod q,

where α⌈ℓ/2⌉,⋅(i,m)(τ)\alpha^{(i,m)}_{\lceil\ell/2\rceil,\cdot}(\tau) denotes a vector in Zqn/k\mathbb{Z}_q^{n/k} indexed by the block variable λu∈[n/k]\lambda_u\in[n/k]. Therefore,

αℓ,v(i,j)(τ+b)−αℓ,v(i,j)(τ)≡∑m∈Zk(αℓ2,v(m,j)(σ+αℓ1,⋅(i,m)(τ+b))−αℓ2,v(m,j)(σ+αℓ1,⋅(i,m)(τ)))(modq).\alpha^{(i,j)}_{\ell,v}(\tau+b)-\alpha^{(i,j)}_{\ell,v}(\tau)\equiv\sum_{m\in\mathbb{Z}_k}\left(\alpha^{(m,j)}_{\ell_2,v}\left(\sigma+\alpha^{(i,m)}_{\ell_1,\cdot}(\tau+b)\right)-\alpha^{(m,j)}_{\ell_2,v}\left(\sigma+\alpha^{(i,m)}_{\ell_1,\cdot}(\tau)\right)\right)\pmod q.

Applying the induction hypothesis successively twice to the inner term, we get

≡∑m∈Zku∈Zn:ru=mw∈Zn:rw=ibλw(A(1..ℓ1))w,u(A(ℓ1+1..ℓ))u,v(modq).\equiv\sum_{\substack{m\in\mathbb{Z}_k\\u\in\mathbb{Z}_n:r_u=m\\w\in\mathbb{Z}_n:r_w=i}}b_{\lambda_w}\left(A^{(1..\ell_1)}\right)_{w,u}\left(A^{(\ell_1+1..\ell)}\right)_{u,v}\pmod q.

Reordering sums,

≡∑w∈Zn:rw=ibxw∑u∈Zn(A(1…ℓ1))w,u(A(ℓ1+1…ℓ))u,v(modq).\equiv\sum_{\substack{w\in\mathbb{Z}_n:\\ r_w=i}} b_{x_w}\sum_{u\in\mathbb{Z}_n}(A^{(1\ldots\ell_1)})_{w,u}(A^{(\ell_1+1\ldots\ell)})_{u,v}\pmod q.

By matrix multiplication,

≡∑w∈Zn:rw=ibxw(A(1…ℓ))w,v(modq).\equiv\sum_{\substack{w\in\mathbb{Z}_n:\\ r_w=i}} b_{x_w}(A^{(1\ldots\ell)})_{w,v}\pmod q.

Hence,

αℓ,v(i,j)(τ+b)−αℓ,v(i,j)(τ)≡∑w∈Zn:rw=ibxw⋅(A(1)A(2)⋯A(ℓ))w,v(modq).\alpha_{\ell,v}^{(i,j)}(\tau+b)-\alpha_{\ell,v}^{(i,j)}(\tau)\equiv\sum_{\substack{w\in\mathbb{Z}_n:\\ r_w=i}}b_{x_w}\cdot(A^{(1)}A^{(2)}\cdots A^{(\ell)})_{w,v}\pmod q.

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 nn vertex directed graph G=(V,E)G=(V,E) with polynomially bounded edge weights W:E→ZW:E\to\mathbb{Z}, and any two designated vertices s,t∈Vs,t\in V, we can compute the minimum weight of an ss-tt walk in sublinear CLP, assuming there is no negative cycle in the graph.

From Theorem 3.1, we know that we can compute AℓA^\ell where AA is an n×nn\times n matrix and ℓ≤n\ell\le n, in CTISP[poly⁡(n,klog⁡ℓ),O(log⁡ℓ⋅log⁡k+log⁡n),O(nk⋅log⁡2n)]\left[\operatorname{poly}(n,k^{\log\ell}),O(\log\ell\cdot\log k+\log n),O\left(\frac{n}{k}\cdot\log^2 n\right)\right].

Therefore, we can compute A2log⁡nA^{2^{\sqrt{\log n}}} in CTISP[poly⁡(n),O(log⁡n),O(n2Θ(log⁡n))]\left[\operatorname{poly}(n),O(\log n),O\left(\frac{n}{2^{\Theta(\sqrt{\log n})}}\right)\right] (by setting k=2O(log⁡n)k=2^{O(\sqrt{\log n})}). Thus we have the following lemma for short length walks:

Lemma 4.2. Given a directed graph GG on nn vertices (without self-loops) with polynomially bounded edge weights, we can compute the minimum weight of a walk from ss to tt that uses at most 2clog⁡n2^{c\sqrt{\log n}} edges in sublinear CLP for any constant cc.

Proof. Let AA be the weighted adjacency matrix over Z[x]\mathbb{Z}[x] given by

A[u,v]={xw(u,v)(u,v)∈E,1u=v,0otherwise.A[u,v]= \begin{cases} x^{w(u,v)} & (u,v)\in E,\\ 1 & u=v,\\ 0 & \text{otherwise}. \end{cases}

We can compute AℓA^\ell in5 sublinear CLP for all ℓ≤2clog⁡n\ell\le2^{c\sqrt{\log n}}. Observe that every monomial appearing in Aℓ[s,t]A^\ell[s,t] corresponds to an ss-tt walk using at most ℓ\ell edges, and the degree of the monomial equals the total weight of the walk. Therefore, the least degree appearing in Aℓ[s,t]A^{\ell}[s,t] equals the minimum weight of an ss-tt walk using at most ℓ\ell edges. This least degree monomial can be interpolated in logspace through [22]. Setting ℓ=2clog⁡n\ell= 2^{c\sqrt{\log n}} proves the claim.

Let G=(V,E)G = (V,E) be a digraph, and U⊂VU \subset V be a multiset. Then for a path PP of GG, we say that UU hits PP, if V(P)∩U≠∅V(P) \cap U \ne\varnothing. We shall use the following sparsification lemma, which is very similar to [11 Theorem 4.1].

Lemma 4.3. There is an algorithm U\mathcal{U} such that for any directed graph G=(V,E)G = (V,E) on nn vertices, a value γ=Ω(log⁡n)\gamma= \Omega(\log n), and seed σ∈{0,1}(ε+6)log⁡n\sigma\in\{0,1\}^{(\varepsilon+6)\log n} for ε>0\varepsilon> 0, satisfies:

  1. U(G,γ,σ,ε)\mathcal{U}(G,\gamma,\sigma,\varepsilon) returns a multiset Uσ⊂VU_\sigma\subset V of size O(nlog⁡nγ)O\left(\frac{n\log n}{\gamma}\right), in logspace

  1. For any set of at most n2n^2 paths each of length γ\gamma, namely P=(P1,…,Pn2)\mathcal{P} = (P_1,\ldots,P_{n^2}) of GG, we have

Pr⁡σ∈{0,1}(ε+6)log⁡n[∀i≤n2:Uσ hits Pi]>3/4.\Pr_{\sigma\in\{0,1\}^{(\varepsilon+6)\log n}}\left[\forall i \le n^2: U_\sigma\text{ hits }P_i\right] > 3/4.

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 DISTn_n

  1. Input: G=(V,E),∣V∣=n,s,t∈VG = (V,E), |V| = n, s,t \in V.

  2. Fix ε>6\varepsilon> 6, λ←2100log⁡n\lambda\leftarrow2^{100\sqrt{\log n}}.

  3. μ←∞\mu\leftarrow\infty

  4. for σ∈{0,1}(ε+6)log⁡n\sigma\in\{0,1\}^{(\varepsilon+6)\log n} do

  5. Uσ←U(G,λ/2,σ,ε)\quad U_\sigma\leftarrow\mathcal{U}(G,\lambda/2,\sigma,\varepsilon)

  6. Vσ←{s,t}∪Uσ\quad V_\sigma\leftarrow\{s,t\} \cup U_\sigma

  7. Eσ\quad E_\sigma is defined by the following loop:

  8. \quad for u,v∈Vσu,v \in V_\sigma do

  9. (u,v)∈Eσ\qquad(u,v) \in E_\sigma if there is a path from uu to vv using at most λ\lambda edges

  10. Wσ(u,v)←\qquad W_\sigma(u,v) \leftarrow min weight of a path from uu to vv using ≤λ\le\lambda edges ▹\triangleright Lemma 4.2

  11. \quad end for

  12. Gσ←(Vσ,Eσ)\quad G_\sigma\leftarrow(V_\sigma,E_\sigma)

  13. Aσ←\quad A_\sigma\leftarrow weighted adjacency matrix of GσG_\sigma with self-loops.

  14. μσ←\quad\mu_\sigma\leftarrow degree of the minimum-degree term in Aσ∣Vσ∣[s,t]A_\sigma^{|V_\sigma|}[s,t] ▹μσ=∞\triangleright\mu_\sigma= \infty if no such term exists.

  15. μ←min⁡(μ,μσ)\quad\mu\leftarrow\min(\mu,\mu_\sigma)

  16. end for

  17. return μ\mu

Proof of Theorem 4.1. We describe the algorithm in Algorithm 4, and discuss the proof of correctness here.

Fix λ=2clog⁡n\lambda= 2^{c\sqrt{\log n}} for some constant cc to be chosen later. Let ε>6\varepsilon> 6 be fixed, and let Uσ=U(G,γ=λ/2,σ,ε)U_\sigma= \mathcal{U}(G,\gamma= \lambda/2,\sigma,\varepsilon), where σ∈{0,1}(ε+6)log⁡n\sigma\in\{0,1\}^{(\varepsilon+6)\log n} is as in Lemma 4.3.

Define Vσ={s,t}∪UσV_\sigma= \{s,t\} \cup U_\sigma, and let GσG_\sigma be a graph on vertex set VσV_\sigma where (u,v)∈Eσ(u,v) \in E_\sigma iff there is a walk from uu to vv in GG containing at most λ\lambda edges.

Notice that ∣Vσ∣=O(nlog⁡nγ)|V_\sigma| = O\left(\frac{n\log n}{\gamma}\right).

Let ρst=(s=u0,u1,…,uℓ=t)\rho_{st} = (s = u_0,u_1,\ldots,u_\ell= t) be a minimum-weight simple path from ss to tt. Such a path exists whenever tt is reachable from ss, and satisfies ℓ≤n−1\ell\le n - 1. Divide ρst\rho_{st} into consecutive segments of γ\gamma edges (except the last which is at most γ\gamma). Let ℓ′=⌊ℓγ⌋\ell' = \left\lfloor\frac{\ell}{\gamma} \right\rfloor. For i∈{0,1,…,ℓ′−1}i \in\{0,1,\ldots,\ell'-1\}, let ρi\rho^i denote the segment between vertices wi=uγiw_i=u_{\gamma i} and wi+1=uγ(i+1)w_{i+1}=u_{\gamma(i+1)} consisting of exactly γ\gamma edges. Let ρℓ′\rho^{\ell'} consist of the edges after wℓ′w_{\ell'} i.e. uℓ−ℓ mod γ,…,uℓ=tu_{\ell-\ell\bmod\gamma},\ldots,u_\ell=t – which consists of less than γ\gamma edges. Let P={ρi}0≤i<ℓ′P=\{\rho^i\}_{0\le i<\ell'}. By Lemma 4.3, with probability at least 3/43/4, every segment ρi\rho^i contains a vertex vi∈Uσv_i\in U_\sigma (for i∈0,…,ℓ′−1i\in0,\ldots,\ell'-1).

For consecutive vertices vi,vi+1v_i,v_{i+1}, the subpath of ρst\rho_{st} between them uses at most 2γ=λ2\gamma=\lambda edges. Hence (vi,vi+1)∈Eσ(v_i,v_{i+1})\in E_\sigma. Notice that the number of edges between s,v0s,v_0 is at most γ\gamma and the number of edges between vℓ′−1,tv_{\ell'-1},t is at most 2γ2\gamma. All other pairs vi,vi+1v_i,v_{i+1} are separated by at most 2γ2\gamma edges. (s,v0,…,vℓ′−1,t)(s,v_0,\ldots,v_{\ell'-1},t) is a path in GσG_\sigma. Assign weights to edges of GσG_\sigma by Wσ:Eσ→ZW_\sigma:E_\sigma\to\mathbb{Z}, where Wσ(u,v)W_\sigma(u,v) is the minimum weight of a path from uu to vv using at most λ\lambda edges.

The subpath of ρst\rho_{st} between any two consecutive vertices among s,v0,…,vℓ′−1,ts,v_0,\ldots,v_{\ell'-1},t uses at most λ\lambda edges. Hence the corresponding edge of GσG_\sigma has weight at most the weight of that subpath. Summing over all segments shows that the minimum-weight path from ss to tt in GσG_\sigma has weight at most the minimum-weight path weight in GG.

Conversely, every edge (u,v)∈Eσ(u,v)\in E_\sigma corresponds to a path in GG from uu to vv of weight exactly Wσ(u,v)W_\sigma(u,v). Therefore any path in GσG_\sigma can be expanded into a walk in GG 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 ss to tt in GσG_\sigma has weight at least the minimum-weight path weight in GG. Hence the minimum-weight path from ss to tt in GσG_\sigma has exactly the same weight as the minimum-weight path from ss to tt in GG.

Let AσA_\sigma be the weighted adjacency matrix of GσG_\sigma given by

Aσ[u,v]={xWσ(u,v)u≠v and (u,v)∈Eσ,1u=v,0otherwise.A_\sigma[u,v]= \begin{cases} x^{W_\sigma(u,v)} & u\ne v\text{ and }(u,v)\in E_\sigma,\\ 1 & u=v,\\ 0 & \text{otherwise}. \end{cases}

Using Lemma 4.2, we can compute AσA_\sigma in sublinear CLP.

We now compute Aσ∣Vσ∣[s,t]A_\sigma^{|V_\sigma|}[s,t]. Let this polynomial be pσ(x)p_\sigma(x). The least degree appearing in pσ(x)p_\sigma(x) equals the minimum weight of an ss-tt path in GσG_\sigma. Suppose this degree is μσ\mu_\sigma. If pσ≡0p_\sigma\equiv0, we set μσ=∞\mu_\sigma=\infty. We enumerate all seeds σ∈{0,1}(ε+6)log⁡n\sigma\in\{0,1\}^{(\varepsilon+6)\log n} and return μ=min⁡σμσ\mu=\min_\sigma\mu_\sigma. For at least one good seed, the previous argument shows that μσ\mu_\sigma equals the minimum weight of an ss-tt path in GG. Therefore μ\mu is exactly the minimum weight of an ss-tt path in GG. The catalytic space used is

O(∣Uσ∣poly⁡(log⁡n))=n2Θ(log⁡n)O(|U_\sigma|\operatorname{poly}(\log n))=\frac{n}{2^{\Theta(\sqrt{\log n})}}

for a sufficiently large choice of cc. The workspace is clearly O(log⁡n)O(\log n), and the running time is polynomial.

Corollary 4.3.1. (Negative cycle detection) Given an nn-vertex directed graph G=(V,E)G=(V,E) with polynomially bounded integer edge weights, we can decide whether GG contains a negative-weight cycle in sublinear CLP.

Proof. We use the same construction as in Theorem 4.1, building for each seed σ\sigma the compressed graph Gσ=(Vσ,Eσ)G_\sigma=(V_\sigma,E_\sigma) with weights W(u,v)W(u,v) defined as the minimum weight of a uu-vv walk using at most λ\lambda edges. But before that if tr⁡(Aλ)\operatorname{tr}(A^\lambda) already contained a monomial with a negative exponent then we have detected a negative cycle.

Let AσA_\sigma be the weighted adjacency matrix:

Aσ[u,v]={xWσ(u,v)(u,v)∈Eσ,1u=v,0otherwise.A_\sigma[u,v] = \begin{cases} x^{W_\sigma(u,v)} & (u,v) \in E_\sigma,\\ 1 & u=v,\\ 0 & \text{otherwise}. \end{cases}

Consider pσ(x)=tr⁡(Aσ∣Vσ∣)p_\sigma(x)=\operatorname{tr}(A_\sigma^{|V_\sigma|}), i.e., the sum of diagonal entries of Aσ∣Vσ∣A_\sigma^{|V_\sigma|}.

Observation 4.4. Every monomial in pσ(x)p_\sigma(x) corresponds to a closed walk in GσG_\sigma of length at most ∣Vσ∣|V_\sigma|, and the degree of the monomial equals the total weight of the walk.

Claim 4.5. GG contains a negative-weight cycle iff for some seed σ\sigma, the polynomial pσ(x)p_\sigma(x) contains a monomial of negative degree or tr⁡(Aλ)\operatorname{tr}(A^\lambda) contains one such monomial where AA is the adjacency matrix of the original graph.

Proof. (1) If a negative cycle exists. Let CC be a negative-weight cycle in GG. By the same hitting-set argument as in Theorem 4.1, with probability at least 3/43/4, all segments of CC are represented in GσG_\sigma, so CC induces a corresponding closed walk in GσG_\sigma with total weight upper bounded by that of CC.

Since CC has negative weight, repeating it yields closed walks of negative total weight. In particular, within the length bound ∣Vσ∣|V_\sigma|, there exists a closed walk whose corresponding monomial in pσ(x)p_\sigma(x) has negative degree, since self loops are allowed.

(2) If no negative cycle exists. Then every cycle in GG 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 pσ(x)p_\sigma(x) have nonnegative degree.

Thus no negative-degree monomial appears. Therefore, GG contains a negative cycle iff for some seed σ\sigma, the polynomial pσ(x)p_\sigma(x) contains a monomial of negative degree or there is a short negative cycle containing at most λ\lambda edges. We enumerate all seeds σ∈{0,1}(ε+6)log⁡n\sigma\in\{0,1\}^{(\varepsilon+6)\log n} 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 G=(V,E)G=(V,E), polynomially bounded W:E→N>0W:E\to\mathbb{N}_{>0} and vertices s,t∈Vs,t\in V, outputs a shortest ss to tt path (if it exists) in sublinear CLP.

Proof. We shall in fact show how to find the lexicographically first ss to tt shortest path. Suppose the lex-first shortest path is (v0=s,v1,…,vℓ−1,vℓ=t)(v_0=s,v_1,\ldots,v_{\ell-1},v_\ell=t). At the ithi^{\text{th}} step, we store viv_i in the worktape. Now, to find vi+1v_{i+1}, we enumerate over all out-neighbors of viv_i and pick the lex-first uu such that W(vi,u)+dist⁡(u,t)=dist⁡(vi,t)W(v_i,u)+\operatorname{dist}(u,t)=\operatorname{dist}(v_i,t), and set vi+1←uv_{i+1}\leftarrow u. To compute dist⁡\operatorname{dist}, 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.

det⁡(A)=[tn]exp⁡(∑k=1n(−1)k+1pkktk)(modtn+1).(1)\det(A) = [t^n]\exp\left(\sum_{k=1}^{n}(-1)^{k+1}\frac{p_k}{k}t^k\right)\pmod{t^{n+1}}. \tag*{(1)}

This brings us to the following.

Theorem 5.1. Let AA be an n×nn \times n matrix over integers. Given AA, A2,…,AnA^2,\ldots,A^n, the value det⁡(A)\det(A) is computable in DLOGTIME-uniform TC0⊆L\mathrm{TC}^0 \subseteq\mathrm{L}.

Proof. From the given powers we first compute

pk=tr⁡(Ak),1≤k≤n,p_k = \operatorname{tr}(A^k), \qquad1 \leq k \leq n,

which is just an iterated sum and hence is in uniform TC0\mathrm{TC}^0. By eq. (1),

det⁡(A)=[tn]∑j=0n(∑k=1n(−1)k+1tr⁡(Ak)ktk)jj!.\det(A) = [t^n]\sum_{j=0}^{n}\frac{\left(\sum_{k=1}^{n}(-1)^{k+1}\frac{\operatorname{tr}(A^k)}{k}t^k\right)^j}{j!}.

Thus the determinant is the coefficient of tnt^n in a polynomial of degree n2n^2 over rationals. So we need to plug in n2+1n^2+1 distinct values for tt and do Lagrange interpolation to recover the coefficient of tnt^n. Consider the rationals that occur in the expression for the polynomial and their denominators (namely j!,kj!, k for j,k≤nj,k \leq n) and observe that none of the denominators has a prime factor exceeding nn. Moreover the numerator and denominator of any rational whose sum constitutes a coefficient of tnt^n is bounded by 2nc2^{n^c} for some constant cc. Thus we can do Chinese remaindering with polynomially many primes each of which is polynomially bounded in nn and greater than n2n^2 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 TC0\mathrm{TC}^0 which is contained in L\mathrm{L}, completing the proof.7

Therefore we have the following as corollary.

Corollary 5.1.1. Let AA be an n×nn \times n matrix over integers, and k∈[1,n]k \in[1,n] a parameter. Then, det⁡(A)\det(A) can be computed in

CTISP[poly⁡(nlog⁡(3k)),O(log⁡n⋅log⁡(3k)),O(nk⋅log⁡2n)].\mathrm{CTISP}\left[\operatorname{poly}\left(n^{\log(3k)}\right),\mathcal{O}(\log n \cdot\log(3k)),\mathcal{O}\left(\frac{n}{k}\cdot\log^2 n\right)\right].

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,

Pf⁡(A)=[tm]exp⁡(12⋅∑k=1m(−1)k+1tr⁡(Bk)ktk)(modtm+1),(2)\operatorname{Pf}(A) = [t^m]\exp\left(\frac{1}{2}\cdot\sum_{k=1}^{m}(-1)^{k+1}\frac{\operatorname{tr}(B^k)}{k}t^k\right)\pmod{t^{m+1}}, \tag*{(2)}

where m=n/2m=n/2, for some even integer nn, and B=−JAB=-JA. Here JJ is a fixed skew symmetric integer matrix depending only on nn, see Section B.2 for more details. Using this notation we have the following.

Theorem 5.3. Let AA be a n×nn\times n skew symmetric matrix over integers. Given AA, BB, B2B^2, …\ldots, BmB^m, the value Pf⁡(A)\operatorname{Pf}(A) is computable by DLOGTIME-uniform TC0\mathrm{TC}^0 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 AA be a skew symmetric n×nn\times n matrix over integers, with nn even, and k∈[1,n]k\in[1,n] a parameter. Then, Pf⁡(A)\operatorname{Pf}(A) can be computed in

CTISP⁡[poly⁡(nlog⁡(3k)),O(log⁡n⋅log⁡(3k)),O(nk⋅log⁡2n)].\operatorname{CTISP}\left[\operatorname{poly}\left(n^{\log(3k)}\right),\mathcal{O}\left(\log n\cdot\log(3k)\right),\mathcal{O}\left(\frac{n}{k}\cdot\log^2 n\right)\right].

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 G=(V,E)G=(V,E) on nn vertices, and a polynomially bounded weight assignment Winput:E→[nc]W_{\mathrm{input}}:E\to[n^c], we can compute a minimum weight perfect matching of GG in near linear CLP.

Proof. Notice first that [23, 29] and Corollary 5.3.1 (setting k=1k=1) immediately give a way to count the number of min-weight perfect matchings of GG 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 GG be a planar bipartite graph. Miller & Naor [27] (see also [15]) had proved that detecting a perfect matching in an nn 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 O(n)\mathcal{O}(n) 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 (G=(V,E),c:E→N∪{0},d:V→Z)(G = (V, E), c : E \to\mathbb{N} \cup\{0\}, d : V \to\mathbb{Z}) where the image of c,dc,d 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 O(∣V∣)O(|V|) vertices with unary integer weights and to distance in a planar digraph on O(∣V∣)O(|V|) 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 nn 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 DD is an (N,Δ,α)(N,\Delta,\alpha)-expander graph if it is a Δ\Delta-regular connected graph on NN vertices, and the second largest eigenvalue (the absolute value) of its normalized adjacency matrix is bounded by α\alpha (0≤α≤10 \le\alpha\le1).

Lemma A.1 ([26, 28]). For every prime pp and every positive integer kk, there exists an infinite family of expander graphs {DN}N\{D_N\}_N, such that each DND_N is an (N,Δ,α)(N,\Delta,\alpha)-expander for Δ=pk+1\Delta= p^k + 1 and α≤2Δ−1Δ\alpha\le\frac{2\sqrt{\Delta-1}}{\Delta}. Furthermore, there is a logspace algorithm (with simultaneous polylogarithmic runtime) that, given, v∈{0,1}log⁡Nv \in\{0,1\}^{\log N} and i∈[Δ]i \in[\Delta], computes the ithi^{\text{th}} neighbor of vv in DND_N.

Definition A.1 (Expander random walk). For any (N,Δ,α)(N,\Delta,\alpha)-expander D=(VD,ED)D=(V_D,E_D), an expander random walk of length K−1K-1 is (X1,…,XK)(X_1,\ldots,X_K) where X1X_1 is the uniform distribution over [N][N], and for every i>1i>1, XiX_i is the uniform distribution over the Δ\Delta-sized neighborhood of the (i−1)th(i-1)^{\text{th}}-vertex in the random walk.

Expander random walks of length KK over [N][N] behaves similar to uniformly sampling KK elements from [N][N], as follows:

Lemma A.2. Let DD be an (N,Δ,α)(N,\Delta,\alpha)-expander, and let B⊂VDB \subset V_D with β=∣B∣N\beta= \frac{|B|}{N}. Then, for every KK, the probability that an expander random walk (X1,…,XK)(X_1,\ldots,X_K) of length (K−1)(K-1) in DD never leaves BB, is at most β(β+α⋅(1−β))K−1\beta(\beta+\alpha\cdot(1-\beta))^{K-1}.

Lemma A.3 ([Vad12]). For every m,n∈Nm,n \in\mathbb{N}, there exists a pairwise independent hash function family Hm,n\mathcal{H}_{m,n}, where a random function can be sampled from Hm,n\mathcal{H}_{m,n} using a seed rr of bitlength max⁡{log⁡m,log⁡n}+log⁡n\max\{\log m,\log n\}+\log n.

Moreover, given any h∈Hm,nh \in\mathcal{H}_{m,n} (described by a string in {0,1}r\{0,1\}^r) and x∈[m]x \in[m], h(x)h(x) can be computed in time poly⁡(log⁡m,log⁡n)\operatorname{poly}(\log m,\log n) and space O(r)O(r).

Next, we have the following lemma about a pairwise independent hash function family Hm,n\mathcal{H}_{m,n}. We say that a hash function hh hits a set B⊆[n]B \subseteq[n], if Im⁡(h)\operatorname{Im}(h) intersects BB. [11] shows that a randomly chosen hh from Hm,n\mathcal{H}_{m,n}, where m=O(n/γ)m=O(n/\gamma), hits any γ\gamma-sized subset of [n][n] with large probability.

Lemma A.4 ([11]). For any constant 0<β<1/20<\beta<1/2, let m=n(1/β)γm=\frac{n^{(1/\beta)}}{\gamma}, and let Hm,n\mathcal{H}_{m,n} be a pairwise independent hash function family from [m][m] to [n][n]. Then, for any B⊂[n]B \subset[n] of size γ\gamma we have,

Pr⁡h∼Hm,n[h hits B]≥1−β.\Pr_{h\sim\mathcal{H}_{m,n}}[h\text{ hits }B] \ge1-\beta.

Finally, we prove Lemma 4.3.

Proof of Lemma 4.3. For a fixed γ=Ω(log⁡n)\gamma= \Omega(\log n) and small enough β∈(0,1/2)\beta\in(0,1/2) to be fixed later, let m=n(1/β)γm = \frac{n^{(1/\beta)}}{\gamma}, N=∣Hm,n∣N = |\mathcal{H}_{m,n}|, and D=(VD,ED)D = (V_D, E_D) be an (N,Δ=1+1/β2,α)(N, \Delta= 1 + 1/\beta^2, \alpha)-expander given by Lemma A.1 (assume that β−1\beta^{-1} is a prime power). Observe that by the choice of Δ\Delta and the fact that α≤2Δ−1Δ\alpha\le\frac{2\sqrt{\Delta-1}}{\Delta}, we have α≤2β\alpha\le2\beta.

In UU, UσU_\sigma is constructed as follows: Use log⁡N\log N bits to identify a vertex h1h_1 of DD, this is like uniformly sampling from X1X_1 which is the random variable for a vertex of DD. Next, sample a K−1K-1-expander random walk using Klog⁡ΔK\log\Delta bits to get (h1,…,hK)∼(X1,…,XK)(h_1,\ldots,h_K) \sim(X_1,\ldots,X_K). This takes log⁡N+Klog⁡Δ\log N + K\log\Delta bits. log⁡N≤2log⁡n\log N \le2\log n since m<nm<n for small enough β\beta. Again it can be seen (as in [11]) that for small enough β\beta, setting K=(2+ε/8)log⁡nlog⁡(1/3β)K = \frac{(2+\varepsilon/8)\log n}{\log(1/3\beta)}, we have 2log⁡n+Klog⁡Δ≤(ε+6)log⁡n2\log n + K\log\Delta\le(\varepsilon+6)\log n i.e. the seed σ∈{0,1}(ε+6)log⁡n\sigma\in\{0,1\}^{(\varepsilon+6)\log n}. Finally, Uσ=⋃i∈[K]Im⁡hiU_\sigma= \bigcup_{i\in[K]}\operatorname{Im} h_i, and thus we have ∣Uσ∣≤K⋅m=O(nlog⁡nγ)|U_\sigma| \le K\cdot m = O\left(\frac{n\log n}{\gamma}\right).

Let B\mathcal{B} be the subset of VDV_D in DD that contains hash functions in Hm,n\mathcal{H}_{m,n} that do not hit P1P_1. Applying Lemma A.4 for subsets of size γ\gamma, we see that ∣B∣/N≤β|\mathcal{B}|/N \le\beta.

Now, using the property of an expander random walks, Lemma A.2 and the fact that α≤2β\alpha\le2\beta, we have

Pr⁡(h1,…,hK)∼(X1,…,XK)[∀i∈[K],Im⁡(hi)∩V(P1)=ϕ]≤β⋅(β+α⋅(1−β))K−1≤β⋅(β+2β⋅(1−β))K−1≤(3β)K\Pr_{(h_1,\ldots,h_K)\sim(X_1,\ldots,X_K)}\left[\forall i\in[K],\operatorname{Im}(h_i)\cap V(P_1)=\phi\right] \le\beta\cdot\left(\beta+\alpha\cdot(1-\beta)\right)^{K-1} \le\beta\cdot\left(\beta+2\beta\cdot(1-\beta)\right)^{K-1}\le(3\beta)^K

Again, since K=(2+ε/8)log⁡(n)log⁡(1/3β)K = \frac{(2+\varepsilon/8)\log(n)}{\log(1/3\beta)}, the probability that P1P_1 does not intersect with UσU_\sigma is at most 1n2+ε/8\frac{1}{n^{2+\varepsilon/8}}. Applying the union bound over all paths Pi∈PP_i\in\mathcal{P}, we have that:

Pr⁡σ∈{0,1}(ε+6)log⁡n[∀i≤n2:Uσ∩V(Pi)≠ϕ]≥1−1nε/8>34.\Pr_{\sigma\in\{0,1\}^{(\varepsilon+6)\log n}}\left[\forall i\le n^2: U_\sigma\cap V(P_i)\ne\phi\right]\ge1-\frac{1}{n^{\varepsilon/8}}>\frac34.

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 x1,…,xnx_1,\ldots,x_n be variables, denote for k≥1k\ge1 by pk(x1,…,xn)p_k(x_1,\ldots,x_n) the kk-th power sum:

pk(x1,…,xn)=∑i=1nxik=x1k+⋯+xnk,p_k(x_1,\ldots,x_n)=\sum_{i=1}^{n}x_i^k=x_1^k+\cdots+x_n^k,

and for k≥0k \ge0 denote by ek(x1,…,xn)e_k(x_1,\ldots,x_n) the elementary symmetric polynomial, that is, the sum of all distinct products of kk distinct variables, so

e0(x1,…,xn)=1,e1(x1,…,xn)=x1+x2+⋯+xn,e2(x1,…,xn)=∑1≤i<j≤nxixj,⋮en(x1,…,xn)=x1x2⋯xn,ek(x1,…,xn)=0,for k>n.\begin{aligned} e_0(x_1,\ldots,x_n) &= 1,\\ e_1(x_1,\ldots,x_n) &= x_1+x_2+\cdots+x_n,\\ e_2(x_1,\ldots,x_n) &= \sum_{1\le i<j\le n} x_i x_j,\\ &\vdots\\ e_n(x_1,\ldots,x_n) &= x_1x_2\cdots x_n,\\ e_k(x_1,\ldots,x_n) &= 0,\quad\text{for } k>n. \end{aligned}

Let λ1,…,λn\lambda_1,\ldots,\lambda_n be the eigenvalues of the matrix AA. We know that sum of eigenvalues of a matrix is equal to its trace and eigenvalues of AℓA^\ell are the eigenvalues of AA raised to the power ℓ\ell, for more details refer to any standard linear algebra textbook.

Then from the above two facts, we get tr⁡(Aℓ)≡∑i=1nλiℓ(modq)\operatorname{tr}(A^\ell)\equiv\sum_{i=1}^{n}\lambda_i^\ell\pmod q, which we can compute using the matrix powering algorithm from 3.1. Thus ∑i=1nλiℓ\sum_{i=1}^{n}\lambda_i^\ell, for 1≤ℓ≤n1\le\ell\le n, are our power sums and from these we will compute the nnth elementary symmetric polynomial ∏i=1nλi\prod_{i=1}^{n}\lambda_i, which is equal to the determinant of the matrix AA.

The ordinary generating function of the elementary symmetric polynomials is

E(t):=∑j=0nej(λ1,…,λn)tj=∏i=1n(1+λit)=det⁡(I+tA).E(t):=\sum_{j=0}^{n}e_j(\lambda_1,\ldots,\lambda_n)t^j=\prod_{i=1}^{n}(1+\lambda_i t)=\det(I+tA).

Taking logarithms as formal power series gives (see Stanley [Sta99, Chapter 7, Equation (7.23)])

log⁡E(t)=∑i=1nlog⁡(1+λit)=∑i=1n∑k≥1(−1)k+1λiktkk=∑k≥1(−1)k+1pkktk.\log E(t)=\sum_{i=1}^{n}\log(1+\lambda_i t)=\sum_{i=1}^{n}\sum_{k\ge1}(-1)^{k+1}\frac{\lambda_i^k t^k}{k}=\sum_{k\ge1}(-1)^{k+1}\frac{p_k}{k}t^k.

Hence we have,

det⁡(I+tA)=exp⁡(∑k≥1(−1)k+1tr⁡(Ak)ktk).\det(I+tA)=\exp\left(\sum_{k\ge1}(-1)^{k+1}\frac{\operatorname{tr}(A^k)}{k}t^k\right).

Since det⁡(I+tA)\det(I+tA) has degree at most nn, the coefficient of tnt^n is obtained from the truncation modulo tn+1t^{n+1}, thus yielding eq. (1).

Pfaffian

Fix the 2×22\times2 matrix:

J2=(01−10).J_2=\begin{pmatrix}0&1\\-1&0\end{pmatrix}.

and JJ be a block diagonal matrix of size n×nn\times n as J=diag⁡(J2,…,J2)J=\operatorname{diag}(J_2,\ldots,J_2). We have Pf⁡(J)=1\operatorname{Pf}(J)=1, det⁡(J)=1\det(J)=1 and J−1=−JJ^{-1}=-J.

Consider Q(t)=Pf⁡(J+tA)Q(t)=\operatorname{Pf}(J+tA), which is valid since the matrix J+tAJ+tA is skew symmetric too. Every term in a Pfaffian is a product of mm matrix entries. Therefore Q(t)Q(t) has degree at most mm, and choosing the tAtA contribution from every factor gives [tm]Q(t)=Pf⁡(A)[t^m]Q(t)=\operatorname{Pf}(A).

By Cayley’s theorem Q(t)2=det⁡(J+tA)Q(t)^2=\det(J+tA). Set B=J−1A=−JAB=J^{-1}A=-JA. Then we have

Q(t)2=det⁡J⋅det⁡(I+tB)=det⁡(I+tB).Q(t)^2=\det J\cdot\det(I+tB)=\det(I+tB).

Since Q(0)=Pf⁡(J)=1Q(0)=\operatorname{Pf}(J)=1, it is the unique formal square root with constant term 1, thus we have

Q(t)=det⁡(I+tB).Q(t)=\sqrt{\det(I+tB)}.

From the determinant identity we derived in the previous section, we get

det⁡(I+tB)=exp⁡(12⋅∑k≥1(−1)k+1tr⁡(Bk)ktk)\sqrt{\det(I+tB)}=\exp\left(\frac{1}{2}\cdot\sum_{k\geq1}(-1)^{k+1}\frac{\operatorname{tr}(B^k)}{k}t^k\right)

and consequently we get eq. (2).

Remaining part of Proof of Theorem 5.4

Theorem 5.4. Given a planar graph G=(V,E)G=(V,E) on nn vertices, and a polynomially bounded weight assignment Winput:E→[nc]W_{\mathrm{input}}:E\to[n^c], we can compute a minimum weight perfect matching of GG in near linear CLP.

Proof. Now, consider an extra block of catalytic space consisting of 100mlog⁡m100m\log m 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):

  1. Let free←0free\leftarrow0 be the amount of free space available to us from the catalytic tape.

  1. Read the first 10mlog⁡m10m\log m bits after freefree number of bits on the catalytic tape, as a weight assignment: W(e1),…,W(em)W(e_1),\ldots,W(e_m), W:E→[m10]W:E\to[m^{10}]. Check if the weight assignment W^=MWinput+W\widehat{W}=MW_{\mathrm{input}}+W min-isolates a perfect matching in GG (use the counting oracle to do this, done in [2]), where M=nm10M=nm^{10} is a large constant.

  1. Suppose W^\widehat{W} is indeed a min-isolating weight assignment. Then output the unique min-weight matching w.r.t W^\widehat{W}, 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.

  1. Suppose WW is not isolating, then we find a threshold edge eie_i (use [2]), and replace WW with (freespace,i,W(e1),…,W(ei−1),W(ei+1),…,W(em))(freespace,i,W(e_1),\ldots,W(e_{i-1}),W(e_{i+1}),\ldots,W(e_m)) where free←free+9log⁡mfree\leftarrow free+9\log m is currently the number of free bits available (which is 10mlog⁡m−log⁡m−10(m−1)log⁡m10m\log m-\log m-10(m-1)\log m), and freespacefreespace is just freefree-many bits available to us for any computation. At this stage, either free≤100mlog⁡m−10mlog⁡mfree\leq100m\log m-10m\log m or not. If free≤90mlog⁡mfree\leq90m\log m, 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 mm edges, i.e. uses at most mlog⁡mm\log m space. This can be done in the freespacefreespace. Finally go to step 5 to reconstruct the catalytic tape.

  1. To reconstruct the catalytic tape, we decompress the weight assignments backwards, i.e, consider the first log⁡m+10(m−1)log⁡m\log m+10(m-1)\log m-bits after the freespacefreespace (freefree number of bits): (i,W(e1),…,W(ei−1),W(ei+1),…,W(em))(i,W(e_1),\ldots,W(e_{i-1}),W(e_{i+1}),\ldots,W(e_m)). Compute the weight of the threshold edge eie_i ([2]), and replace it with (W(e1),…,W(ei),…,W(em))(W(e_1),\ldots,W(e_i),\ldots,W(e_m)) and subtract free←free−9log⁡mfree\leftarrow free-9\log m. Repeat this process, until free=0free=0, i.e. when the catalytic tape has finally been restored.

To fill in the details, we refer [2]. The above clearly requires O(nlog⁡2n+mlog⁡m)=O(nlog⁡2n)O(n\log^2 n+m\log m)=O(n\log^2 n) 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 AA has a negative demand of −1-1 (i.e. a surplus of 1) and every vertex in the other bipartition BB a positive demand of +1+1. On the other hand every arc (a,b)(a,b) has capacity c(a,b)=1c(a,b)=1 while the reverse arc (b,a)(b,a) has a capacity c(a,b)=0c(a,b)=0 a∈Aa \in A, b∈Bb \in B.

In order to construct such a flow function ff, they first ignore the capacities and find a flow f(0)f^{(0)} in the network G(0)G^{(0)} satisfying the demands. To do so, they construct a spanning tree TT in the network and make sure that every edge e={u,v}e=\{u,v\} carries a flow equal to the sum of the demands in the subtree containing vv formed by deleting the edge ee 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 uu side subtree of T−eT-e. It also means f(0)f^{(0)} is skew-symmetric.

They then construct a new flow network G(1)G^{(1)} with the capacity of edge ee being c1(e)=c(e)−f(0)(e)c_1(e)=c(e)-f^{(0)}(e) (and for the reverse edge eRe^R, c1(eR)=c(eR)−f(0)(eR)=c(eR)+f(0)(e)c_1(e^R)=c(e^R)-f^{(0)}(e^R)=c(e^R)+f^{(0)}(e)). They go on to construct the directed dual of this network where the dual e∗e^* of the edge ee is obtained by turning the edge ee, clockwise. The weight w(e∗)=c1(e)w(e^*)=c_1(e). They show that the original flow network has a valid flow iff the dual flow network under the weights ww has no negative cycle.

If the dual does not have a negative cycle, shortest paths are well defined in the dual. Let s∗s^* be an arbitrary vertex in the dual (i.e. a face in the primal). Compute the shortest distance d(s∗,v∗)d(s^*,v^*) from s∗s^* to every vertex v∗v^*. Define f(1)(e)=d(s∗,v∗)−d(s∗,u∗)f^{(1)}(e)=d(s^*,v^*)-d(s^*,u^*) where (u∗,v∗)(u^*,v^*) is the directed dual edge of ee. Then, [27] show that f(1)f^{(1)} is a valid flow in the residual graph c−f(0)c-f^{(0)} i.e. f(1)f^{(1)} is skew-symmetric and f(1)(e)≤c(e)−f(0)(e)f^{(1)}(e)\leq c(e)-f^{(0)}(e) for every edge ee. In other words, f=f(0)+f(1)f=f^{(0)}+f^{(1)} is a valid flow in the original network GG. This is because it is skew-symmetric from the skew-symmetry of f(0)f^{(0)}, f(1)f^{(1)} and satisfies f(e)=f(0)(e)+f(1)(e)≤c(e)f(e)=f^{(0)}(e)+f^{(1)}(e)\leq c(e).

Therefore in conclusion we obtain Theorem 5.5.

References

  1. [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. [2]V. Arvind, Srijan Chakraborty, and Samir Datta. Derandomizing isolation in catalytic logspace. 2026.arxiv.org/abs/2512.09374
  3. [3]Eric Allender and Meena Mahajan. The complexity of planarity testing. Inf. Comput., 189(1):117–134, 2004.
  4. [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. [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. [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. [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. [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. [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. [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. [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. [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. [13]Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Thomas Thierauf. Bipartite matching is in NC. Electron. Colloquium Comput. Complex., TR26, 2026.
  14. [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
  15. [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.
  16. [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.
  17. [18]Roman Edenhofer. A space-space trade-off for directed st-connectivity. 2026.arxiv.org/abs/2602.21088
  18. [19]Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of bodlaender and courcelle. In FOCS, pages 143–152, 2010.DOI
  19. [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
  20. [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.
  21. [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
  22. [23]P W Kastelyn. Graph theory and crystal physics. In F Harary, editor, Graph Theory and Theoretical Physics, pages 43–110. Academic Press, 1967.
  23. [24]Michal Koucký, Ian Mertz, Edward Pyne, and Sasha Sami. Collapsing catalytic classes. CoRR, abs/2504.08444, 2025.arxiv.org/abs/2504.08444
  24. [25]Dexter C. Kozen. Csanky’s Algorithm, pages 166–170. Springer New York, New York, NY, 1992.DOI
  25. [26]Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.
  26. [27]Gary L. Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. SIAM J. Comput., 24(5):1002–1017, 1995.
  27. [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
  28. [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
  29. [30]Noam Nisan. RL ⊆ = SC. Comput. Complex., 4:1–11, 1994.
  30. [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
  31. [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.
  32. [33]Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), September 2008.DOI

Paper details

vlnc:W_tu8nbdyw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Chat GPT Astra

View statement
Looking for related papers…
Contents