# Recursive Error Reduction for Regular Branching Programs

Eshan Chattopadhyay
Cornell University
<EMAIL_ADDRESS>Supported by a Sloan Research Fellowship and NSF CAREER
Award 2045576. Jyun-Jie Liao11footnotemark: 1
Cornell University
<EMAIL_ADDRESS>
(September 08, 2023)

###### Abstract

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved
error reduction framework for the derandomization of regular read-once
branching programs (ROBPs). Their result is based on a clever modification to
the inverse Laplacian perspective of space-bounded derandomization, which was
originally introduced by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford and
Vadhan (FOCS 2020).

In this work, we give an alternative error reduction framework for regular
ROBPs. Our new framework is based on a binary recursive formula from the work
of Chattopadhyay and Liao (CCC 2020), that they used to construct weighted
pseudorandom generators (WPRGs) for general ROBPs.

Based on our new error reduction framework, we give alternative proofs to the
following results for regular ROBPs of length $n$ and width $w$, both of which
were proved in the work of Chen et al. using their error reduction:

  * •

There is a WPRG with error $\varepsilon$ that has seed length

$\tilde{O}(\log(n)(\sqrt{\log(1/\varepsilon)}+\log(w))+\log(1/\varepsilon)).$

  * •

There is a (non-black-box) deterministic algorithm which estimates the
expectation of any such program within error $\pm\varepsilon$ with space
complexity

$\tilde{O}(\log(nw)\cdot\log\log(1/\varepsilon)).$

This was first proved in the work of Ahmadinejad et al., but the proof by Chen
et al. is simpler.

Because of the binary recursive nature of our new framework, both of our
proofs are based on a straightforward induction that is arguably simpler than
the Laplacian-based proof in the work of Chen et al.

In fact, because of its simplicity, our proof of the second result directly
gives a slightly stronger claim: our algorithm computes a
$\varepsilon$-singular value approximation (a notion of approximation
introduced in a recent work by Ahmadinejad, Peebles, Pyne, Sidford and Vadhan
(FOCS 2023)) of the random walk matrix of the given ROBP in space
$\tilde{O}(\log(nw)\cdot\log\log(1/\varepsilon))$. It is not clear how to get
this stronger result from the previous proofs.

##  1 Introduction

A central problem in complexity theory is to understand to what extent is
randomness useful in space-bounded computation. It is widely conjectured that
every randomized algorithm can be made deterministic with only a constant-
factor blowup in space, i.e. ${\mathbf{BPL}}={\mathbf{L}}$. A central approach
to derandomize ${\mathbf{BPL}}$ is to construct explicit pseudorandom
generators (PRGs) for standard-order read-once branching programs (ROBPs),
which we formally define below.

######  Definition 1.1 (ROBPs).

A (standard-order) ROBP $B$ of length $n$ and width $w$ is specified by a
start state $v_{0}\in[w]$, a set of accept states $V_{\mathrm{acc}}$ and $n$
transition functions $B_{i}:[w]\times\\{0,1\\}\overset{}{\rightarrow}{[w]}$
for $i$ from $1$ to $n$. The ROBP $B$ computes a function
$B:\\{0,1\\}^{n}\overset{}{\rightarrow}\\{0,1\\}$ as follows. Given an input
$x\in\\{0,1\\}^{n}$, define $v_{i}=B_{i}(v_{i-1},x_{i})$, where $x_{i}$
denotes the $i$-th bit of $x$. Then output $B(x)=1$ if $v_{n}\in
V_{\mathrm{acc}}$, or $B(x)=0$ otherwise.

######  Remark 1.2.

Equivalently, one can view a ROBP $B$ as a directed graph as follows. Consider
$n+1$ layers of nodes $L_{0},L_{1},\ldots,L_{n}$, each having size $w$, and
label the nodes in each $L_{i}$ with $[w]$. For every
$i\in[n],v\in[w],b\in\\{0,1\\}$, construct an edge with label $b$ from $v$ in
$L_{i-1}$ to $B_{i}(v,b)$ in $L_{i}$. Then the computation of $B(x)$
corresponds to a walk following label $x$ from $L_{0}$ to $L_{n}$. In this
paper we usually consider the equivalent graph view, and we refer to $L_{i}$
as _layer $i$_.

######  Definition 1.3 (PRGs).

Let $\mathcal{F}$ be a class of functions
$f:\\{0,1\\}^{n}\overset{}{\rightarrow}\\{0,1\\}$. An $\varepsilon$-PRG for
$\mathcal{F}$ is a function
$G:\\{0,1\\}^{d}\overset{}{\rightarrow}\\{0,1\\}^{n}$ such that for every
$f\in\mathcal{F}$,

$\left|\operatorname*{\mathbb{E}}_{x\sim\\{0,1\\}^{n}}\left[f(x)\right]-\operatorname*{\mathbb{E}}_{s\sim\\{0,1\\}^{d}}\left[f(G(s))\right]\right|\leq\varepsilon.$

We say $G$ $\varepsilon$-fools the class $\mathcal{F}$ if $G$ is an
$\varepsilon$-PRG for $\mathcal{F}$. We call $d$ the _seed length_ of $G$. We
say $G$ is explicit if it can be computed in space $O(d)$.111Throughout this
paper, when we say a function $f$ is explicit, it means the function $f$ can
be computed in space $O(n)$ where $n$ is the input length.

It can be shown (via probabilistic method) that there exists a
$\varepsilon$-PRG for width-$w$ length-$n$ ROBP with seed length
$O(\log(nw/\varepsilon))$, which is optimal. Furthermore, an _explicit_ PRG
with such seed length would imply ${\mathbf{BPL}}={\mathbf{L}}$. In a seminal
work, Nisan [Nis92] constructed an explicit PRG with seed length
$O(\log(n)\cdot\log(nw/\varepsilon))$, which is only a $O(\log(n))$ factor
away from optimal. Nisan [Nis94] then used this PRG to prove that any problem
in ${\mathbf{BPL}}$ can be deterministically computed in $O(\log^{2}(n))$
space and $\operatorname{poly}(n)$ time. Another remarkable work by Saks and
Zhou [SZ99] also applied Nisan’s generator in a non-trivial way to show that
any problem in ${\mathbf{BPL}}$ can be deterministically computed in
$O(\log^{3/2}(n))$ space.

###  1.1 Weighted PRGs

Despite decades of effort, the seed length of Nisan’s PRG remains the state-
of-the-art for width $w\geq 4$. In fact, even for the $w=3$ special case,
Nisan’s seed length remained unbeatable until a recent work by Meka, Reingold
and Tal [MRT19] which improved the seed length to
$\tilde{O}(\log(n)\log(1/\varepsilon))$. This has motivated researchers to
study relaxed notions of PRGs and their applications in the derandomization of
${\mathbf{BPL}}$. A well-studied notion is that of a hitting set generator
(HSG), which is the “one-sided” variant of a PRG.

######  Definition 1.4 (HSGs).

Let $\mathcal{F}$ be a class of functions
$f:\\{0,1\\}^{n}\overset{}{\rightarrow}\\{0,1\\}$. A $\varepsilon$-PRG for
$\mathcal{F}$ is a function
$G:\\{0,1\\}^{d}\overset{}{\rightarrow}\\{0,1\\}^{n}$ such that for every
$f\in\mathcal{F}$ s.t.
$\operatorname*{\mathbb{E}}_{x\sim\\{0,1\\}^{n}}\left[f(n)\right]>\varepsilon$,
it holds that
$\operatorname*{\mathbb{E}}_{s\sim\\{0,1\\}^{d}}\left[f(G(s))\right]>0$.

The study of explicit HSGs for ROBPs has a long history, starting from the
seminal work by Ajtai, Komlós and Szemerédi [AKS87]. While being weaker than
PRGs, explicit constructions of HSGs can still be used to derandomize
randomized log-space algorithms with one-sided error (${\mathbf{RL}}$). In
fact, a recent work by Cheng and Hoza [CH20] shows that an explicit HSG with
optimal seed length $O(\log(nw/\varepsilon))$ already implies
${\mathbf{BPL}}={\mathbf{L}}$.

In 2018, Braverman, Cohen and Garg [BCG20] introduced another relaxed notion
of PRG called _weighted PRG_ (WPRG). In this relaxed notion, each output
string of $G$ is further assigned a real weight that can _possibly be
negative_.

######  Definition 1.5.

Let $\mathcal{F}$ be a class of functions
$f:\\{0,1\\}^{n}\overset{}{\rightarrow}\\{0,1\\}$. A $\varepsilon$-WPRG is a
pair of functions
$(\rho,G):\\{0,1\\}^{d}\overset{}{\rightarrow}\\{0,1\\}^{n}\times\mathbb{R}$
such that for every $f\in\mathcal{F}$,

$\left|\operatorname*{\mathbb{E}}_{x\sim\\{0,1\\}^{n}}\left[f(x)\right]-\operatorname*{\mathbb{E}}_{s\sim\\{0,1\\}^{d}}\left[\rho(s)\cdot
f(G(s))\right]\right|\leq\varepsilon.$

Surprisingly, by simply allowing negative weights, [BCG20] showed how to
construct an explicit $\varepsilon$-WPRG with seed length

$\tilde{O}(\log(n)\log(nw)+\log(1/\varepsilon)),$

which has almost optimal dependence on $\varepsilon$. A sequence of followup
work [CL20, CDRST21, PV21, Hoz21] further improved the seed length with
simpler WPRG constructions. In particular, Hoza [Hoz21] completely removed the
hidden $\log\log$ factors and improve the seed length to
$O(\log(n)\log(nw)+\log(1/\varepsilon))$.

It was observed in [BCG20] that $\varepsilon$-WPRGs implies
$\varepsilon$-HSGs. In addition, WPRGs seem closer to PRGs than HSGs in the
sense that one can use a WPRG to estimate the expectation of a ROBP $f$ by
simply enumerating all the seeds. In fact, following a suggestion in [BCG20],
[CL20] proved that a WPRG with good enough bound on the output of $\rho$ can
be used in the derandomization framework by Saks and Zhou [SZ99]. Hoza [Hoz21]
then used his WPRG result to prove that ${\mathbf{BPL}}$ can be derandomized
in deterministic space $O(\log^{3/2}(n)/\sqrt{\log\log(n)})$. This was the
first improvement over Saks and Zhou’s decades-old result.

###  1.2 Regular branching programs

For the original notion of PRGs, while there has been no improvement over
Nisan’s seed length for general (standard-order) ROBPs, a lot of progress has
been made in some restricted families. One important example is the setting of
_regular ROBPs_ , which is the main focus of this work.

######  Definition 1.6 (Regular ROBPs).

We say a (standard-order) ROBP $B$ is _regular_ if for every transition
function $B_{i}:[w]\times\\{0,1\\}\overset{}{\rightarrow}{[w]}$ in $B$, every
state $v\in[w]$ has exactly $2$ pre-images.

An important reason to study this family is that general ROBPs can be reduced
to regular ROBPs [RTV06, BHPP22]. In fact, a surprisingly simple proof in a
recent work by Lee, Pyne and Vadhan [LPV23] shows that any function that can
be computed by a ROBP of length $n$ and width $w$ can also be computed by a
regular ROBP of width $O(nw)$.

In 2010, Braverman, Rao, Raz and Yehudayoff proved that the INW generator
[INW94] with proper choices of parameters is in fact a PRG for regular ROBPs
with seed length $O(\log(n)\cdot(\log\log(n)+\log(w/\varepsilon)))$. This is
better than Nisan’s PRG’s seed length when $\log(w/\varepsilon)=o(\log(n))$.
More generally, they introduced the “weight” measure for ROBPs and proved that
an INW generator with fixed parameters has error proportional to the weight.
They then showed that regular ROBPs have smaller weight than general ROBPs
when $w\ll n$, which implies their better seed length bound. (See Section 3
for the formal definitions.) Their better PRG construction for “small-weight”
ROBPs also turns out to be an important ingredient of the PRG for width-3
ROBPs in [MRT19].

Recently, Ahmadinejad, Kelner, Murtagh, Peebles, Sidford and Vadhan [AKMPSV20]
proved a remarkable result that it takes only $\tilde{O}(\log(nw))$ space to
estimate the expectation of a regular ROBP $B$ in a non-black-box way. In
fact, they designed an algorithm that can estimate the expectation of $B$ to
very a high precision without much overhead:

######  Theorem 1.7.

For every $\varepsilon>0$ there is a deterministic algorithm which takes a
regular ROBP $B$ of length $n$ and width $w$ as input, and computes a value
within $\operatorname*{\mathbb{E}}_{x}\left[B(x)\right]\pm\varepsilon$ in
space complexity $\tilde{O}(\log(nw)\log\log(1/\varepsilon))$.

###  1.3 Error reduction for regular branching programs

Given the better PRG by [BRRY14] in the regular setting, it is natural to ask
whether one can get a better WPRG than [Hoz21] in the regular setting too.
This is in fact plausible because the WPRG constructions introduced in Section
1.1 can all be viewed as _error reduction procedures_ : given any
$\varepsilon_{0}$-PRG for ROBPs for some “mild error” $\varepsilon_{0}$ (which
we call the “base PRG”), one can construct a $\varepsilon$-WPRG for ROBPs with
better dependence on $\varepsilon$. For general standard-order ROBPs, The
$O(\log(n)\log(nw)+\log(1/\varepsilon))$ seed length described in Section 3
was obtained by taking Nisan’s PRG as the base PRG. Therefore, it is natural
to think that one can obtain a better $\varepsilon$-WPRG for regular ROBPs by
taking the PRG in [BRRY14] as the base PRG instead.

However, it turns out that the intuition is not trivially true, because every
known error reduction procedure for general ROBPs requires the “base error”
$\varepsilon_{0}$ to be at most $<1/n$. When $\varepsilon_{0}<1/n$, the
$\tilde{O}(\log(n)\log(w/\varepsilon_{0}))$ seed length bound in [BRRY14] is
no better than Nisan’s $O(\log(n)\log(nw/\varepsilon_{0}))$ seed length, so we
cannot hope to get any improvement in the seed length of the corresponding
WPRG.

This problem was recently solved by Chen, Hoza, Lyu, Tal and Wu [CHLTW23].
They showed how to exploit the regular property and obtain a reduction from
$\varepsilon$-WPRG for regular ROBPs to PRG for regular ROBPs with error
$\varepsilon_{0}=O(1/\log^{2}(n))$. As a result, they proved the following
theorem.

######  Theorem 1.8 ([CHLTW23]).

There is an explicit $\varepsilon$-WPRG for regular ROBPs with seed length

$\tilde{O}\left(\log(n)\left(\log(w)+\sqrt{\log(1/\varepsilon)}\right)+\log(1/\varepsilon)\right).$

Following [AKMPSV20, CDRST21, PV21, Hoz21], the WPRG construction in [CHLTW23]
is based on the “inverse Laplacian” perspective of small-space derandomization
and Richardson iteration. The key step in their construction is to modify the
approximated inverse Laplacian based on a structure called “shortcut graph”.
With the shortcut graph structure, they showed how to apply the potential
argument in [BRRY14] to get a better bound for $\varepsilon$ that is still
non-trivial even when $\varepsilon_{0}=O(1/\log^{2}(n))$. Based on the same
idea, [CHLTW23] also showed how to get a simplified proof of the non-black-box
derandomization result in [AKMPSV20] (Theorem 1.7).

In short, the main purpose of using the shortcut graph idea in [CHLTW23] is to
embed a “binary-recursive-like” structure into the inverse Laplacian analysis.
Such a structure makes their analysis compatible with the potential argument
in [BRRY14]. In order to prove the non-black-box derandomization result in
Theorem 1.7, [CHLTW23] showed that one can apply a different potential
argument based on the notion of “singular-value approximation” (SV
approximation) defined in [APPSV23].

###  1.4 Our contribution

While the shortcut graph modification gives a nice structure to the inverse
Laplacian analysis, the inverse Laplacian perspective itself is sometimes
tricky to work with. In fact, although the proof of Theorem 1.7 in [CHLTW23]
is simpler than the original proof in [AKMPSV20], they still need to work on a
sophisticated matrix seminorm, and the corresponding potential argument
requires non-trivial ideas to analyze.

In this work, we give an alternative error reduction framework for regular
ROBPs by modifying a WPRG construction by Chattopadhyay and Liao [CL20]. The
advantage of using [CL20] is that their WPRG construction is _actually binary
recursive_ , and hence is naturally compatible with the weight argument in
[BRRY14]. To construct a WPRG for regular branching program that matches the
parameter in Theorem 1.8, we show that the analysis in [CL20] can be improved
in the regular setting based on the weight argument in [BRRY14]. Inspired by
the proof of Theorem 1.7 in [CHLTW23], we also give an alternative proof of
Theorem 1.7 based on the notion of SV approximation. Because of the binary
recursive nature of [CL20], both proofs are relatively straightforward by
induction and are arguably simpler than the proofs in [CHLTW23].

In fact, our proof of Theorem 1.7 implies a slightly stronger claim (Theorem
4.5) which might be of independent interest: we can compute an
$\varepsilon$-SV approximation of the random walk matrix of any regular ROBP
of width $w$ and length $n$ in space
$\tilde{O}(\log(nw)\log\log(1/\varepsilon))$. (See [APPSV23] for comparison
between SV approximation and other notions of approximation.) It is not clear
how to obtain this stronger claim from the previous proofs of Theorem 1.7
[AKMPSV20, CHLTW23].

Finally, we show in Appendix D that the Laplacian-based construction in
[CHLTW23] is actually equivalent to the binary recursive construction in
[CL20] that we use in this paper. We note that our proofs of Theorem 1.7 and
Theorem 1.8 are self-contained and do not rely on this fact.

######  Remark 1.9.

In addition to Theorem 1.7 and Theorem 1.8, [CHLTW23] also constructed WPRGs
for width-$3$ ROBPs and unbounded-width permutation ROBPs, both having seed
length $\tilde{O}(\log(n)\sqrt{\log(1/\varepsilon)}+\log(1/\varepsilon))$. For
width-$3$ ROBPs, they improved the reduction from width-$3$ to small-weight
ROBPs in [MRT19], and then applied the reduction on their WPRG in Theorem 1.7
which also works for small-weight ROBPs. For unbounded-width permutation
ROBPs, they adapted their proof of Theorem 1.7 to the setting of WPRGs for
permutation ROBPs, similar to what [PV21] did for the proof in [AKMPSV20]. We
note that for both of these results the Theorem 1.7 and Theorem 1.8 parts can
be replaced with our proofs too.

###  1.5 Organization

In Section 2 we introduce some general definitions that are used in both the
proofs of Theorem 1.8 and Theorem 1.7, and give a brief overview of our
proofs. In Section 3 we formally prove Theorem 1.8. In Section 4 we prove
Theorem 1.7.

##  2 General Setup and Proof Overview

#### Notation.

For $n\in\mathbb{N}$, denote $[n]=\\{1,2,\ldots,n\\}$. We write matrices in
boldface and use $\mathbf{M}[i,j]$ to denote the entry of matrix $\mathbf{M}$
on the $i$-th row and the $j$-th column. We use $\mathbf{I}_{w}$ to denote the
$w\times w$ identity matrix. For a column vector $x$, we denote the $i$-th
entry of $x$ by $x[i]$. For every matrix $\mathbf{M}\in\mathbb{R}^{w\times
w}$, $\left\|\mathbf{M}\right\|_{\infty}$ denotes the infinity norm
$\sup_{\left\|v\right\|_{\infty}=1}\left\|\mathbf{M}v\right\|_{\infty}$ and
$\left\|\mathbf{M}\right\|$ denotes the $2$-norm
$\sup_{\left\|v\right\|=1}\left\|\mathbf{M}v\right\|$. For any symbol $\Sigma$
and string $x\in\Sigma^{*}$, we use $\left|x\right|$ to denote the length of
$x$, $x_{[i]}$ to denote the $i$-th symbol of $x$ and $x_{[\leq i]}$ to denote
the prefix of $x$ of length $x$. For any two strings $x,y$, we use $x\circ y$
to denote the concatenation of $x$ and $y$.

###  2.1 ROBPs and matrices

For the rest of this paper, we consider a fixed regular ROBP $B$ of length $n$
and width $w$ specified by transition functions $B_{1},\ldots,B_{n}$. For
every $i\in[n]$, and every $b\in\\{0,1\\}$, define the matrix
$\mathbf{M}_{i}(b)\in\mathbb{R}^{w\times w}$ as

$\forall u,v\in[w],\mathbf{M}_{i}(b)[u,v]:=\begin{cases}1\textrm{ if
}B_{i}(u,b)=v,\\\ 0\textrm{ otherwise.}\end{cases}$

We refer to $\mathbf{M}_{i}(b)$ as the _transition matrix of $B_{i}$ on $b$_.
In addition, for every $0\leq\ell<r\leq n$ and a string
$s\in\\{0,1\\}^{r-\ell}$, we denote the transition matrix from layer $\ell$ to
layer $r$ on input $x$ as

$\mathbf{M}_{\ell..r}(s):=\prod_{i=1}^{r-\ell}\mathbf{M}_{\ell+i}(s_{i})$

In this paper we frequently use the following fact:

######  Fact 1.

For every $\ell<m<r$ and $x\in\\{0,1\\}^{m-\ell},y\in\\{0,1\\}^{r-m}$,
$\mathbf{M}_{\ell..m}(x)\mathbf{M}_{m..r}(y)=\mathbf{M}_{\ell..r}(x\circ y)$.

In addition, observe that for a start state $v_{0}\in[w]$ and a set of accept
state $V_{\mathrm{acc}}\subseteq[w]$, $B(s)=1$ if and only if there exists
$v_{n}\in V_{\mathrm{acc}}$ s.t. $\mathbf{M}_{0..n}(s)[v_{0},v_{n}]=1$.

Given the definitions above, we further define
$\mathbf{M}_{i}:=\frac{1}{2}(\mathbf{M}_{i}(0)+\mathbf{M}_{i}(1))$ which we
call the _random walk matrix_ of $B_{i}$, and define
$\mathbf{M}_{\ell..r}:=\prod_{i=\ell+1}^{r}\mathbf{M}_{i}$ which is the random
walk matrix from layer $\ell$ to layer $r$. Note that
$\left\|\mathbf{M}_{\ell..r}\right\|_{\infty}\leq 1$ because
$\mathbf{M}_{\ell..r}$ is right-stochastic,222This still holds when $B$ is not
regular. and we also have $\left\|\mathbf{M}_{\ell..r}\right\|\leq 1$ because
$\mathbf{M}_{\ell..r}$ is doubly-stochastic by the regularity.

Finally, we define $v_{\mathsf{st}}$ to be the “start vector” s.t.
$v_{\mathsf{st}}[v_{0}]=1$ and $v_{\mathsf{st}}[i]=0$ for every $i\neq v_{0}$,
and $v_{\mathsf{ed}}$ to be the “accept vector” s.t. $v_{\mathsf{ed}}[i]=1$ if
$i\in V_{\mathrm{acc}}$ and $v_{\mathsf{ed}}[i]=0$ otherwise. Then observe
that

$B(s)=v_{\mathsf{st}}^{\top}\mathbf{M}_{0..n}(s)v_{\mathsf{ed}}$

and

$\operatorname*{\mathbb{E}}_{s\in\\{0,1\\}^{n}}\left[B(s)\right]=v_{\mathsf{st}}^{\top}\mathbf{M}_{0..n}v_{\mathsf{ed}}.$

Given these facts, our goal is to find a “good approximation” of
$\mathbf{M}_{0..n}$, denoted by $\widetilde{\mathbf{M}_{0..n}}$, s.t.

$\left|v_{\mathsf{st}}^{\top}\mathbf{M}_{0..n}v_{\mathsf{ed}}-v_{\mathsf{st}}^{\top}\widetilde{\mathbf{M}_{0..n}}v_{\mathsf{ed}}\right|\leq\varepsilon.$

For Theorem 1.8 we want $\widetilde{\mathbf{M}_{0..n}}$ to correspond to the
output of a WPRG with short seed length, while for Theorem 1.7 we want to make
sure that $\widetilde{\mathbf{M}_{0..n}}$ can be implemented in
$\widetilde{O}(\log(nw)\log\log(1/\varepsilon))$ space. Because of the
different goals, the notions of approximation would also be different in the
proofs of Theorem 1.8 and Theorem 1.7.

###  2.2 Recursion

In this section, we introduce a recursive definition from [CL20] which we use
in both the proofs of Theorem 1.8 and Theorem 1.7. Without loss of generality,
we assume that $n$ is a power of $2$ for the rest of this paper. Then define
the set of “binary splitting points” to be

$\mathsf{BS}_{n}=\\{(\ell,r):\exists i,k\in\mathbb{N}\cup\\{0\\}\textrm{ s.t.
}\ell=i\cdot 2^{k}\wedge r=\ell+2^{k}\\}.$

Suppose for every $(\ell_{0},r_{0})\in\mathsf{BS}_{n}$, we have defined a
matrix $\mathbf{M}_{\ell_{0}..r_{0}}^{(0)}$ that is a “mild approximation” of
$\mathbf{M}_{\ell_{0}..r_{0}}$. Then consider the following recursive
definition of matrices for every $(\ell,r)\in\mathsf{BS}_{n}$ and every
$k\in\mathbb{N}$:

$\mathbf{M}_{\ell..r}^{(k)}=\begin{cases}\mathbf{M}_{r}&\textrm{ if
}r-\ell=1,\\\
\sum_{i+j=k}\mathbf{M}_{\ell..m}^{(i)}\cdot\mathbf{M}_{m..r}^{(j)}-\sum_{i+j=k-1}\mathbf{M}_{\ell..m}^{(i)}\cdot\mathbf{M}_{m..r}^{(j)}&\textrm{
otherwise, where $m=(\ell+r)/2$.}\end{cases}$ (1)

The WPRG construction in [CL20] is exactly a derandomization of the matrix
$\mathbf{M}_{0..n}^{(\log(1/\varepsilon))}$, where the base cases
$\mathbf{M}_{\ell_{0}..r_{0}}^{(0)}$ are generated by Nisan’s PRG with error
$1/n$. In this paper, we also prove Theorem 1.8 and Theorem 1.7 by showing
that $\mathbf{M}_{0..n}^{(k)}$ is a good enough approximation of
$\mathbf{M}_{0..n}$ (with different choices of the parameter $k$ and base case
matrices $\mathbf{M}_{\ell_{0}..r_{0}}^{(0)}$).

Now for every $i\geq 0$, define
$\mathbf{\Delta}_{\ell..r}^{(i)}:=\mathbf{M}_{\ell..r}^{(i)}-\mathbf{M}_{\ell..r}$.
The correctness of both [CL20] and our results relies on the following
identity.

######  Lemma 2.1 ([CL20]).

For every $(\ell,r)\in\mathsf{BS}_{n}$ s.t. $r-\ell>1$ and $m=(\ell+r)/2$,

$\mathbf{\Delta}_{\ell..r}^{(k)}:=\sum_{i+j=k}\mathbf{\Delta}_{\ell..m}^{(i)}\cdot\mathbf{\Delta}_{m..r}^{(j)}-\sum_{i+j=k-1}\mathbf{\Delta}_{\ell..m}^{(i)}\cdot\mathbf{\Delta}_{m..r}^{(j)}+\mathbf{\Delta}_{\ell..m}^{(k)}\mathbf{M}_{m..r}+\mathbf{M}_{\ell..m}\mathbf{\Delta}_{m..r}^{(k)}.$

We briefly sketch how the correctness in [CL20] was proved based on the lemma
above. Suppose the “base PRG” has error $\varepsilon_{0}$ so that
$\left\|\mathbf{\Delta}_{\ell_{0}..r_{0}}^{(0)}\right\|_{\infty}\leq\varepsilon_{0}$.
Then one can prove by induction that
$\left\|\mathbf{\Delta}_{0..n}^{(k)}\right\|_{\infty}\leq
O(n\varepsilon_{0})^{k+1}$, i.e. $\mathbf{M}_{0..n}^{(k)}$ is a
$O(n\varepsilon_{0})^{k+1}$-approximation of $\mathbf{M}_{0..n}$, using the
fact that $\left\|\mathbf{M}_{\ell..r}\right\|_{\infty}\leq 1$ for every
$\ell<r$.

Now observe that the $O(n\varepsilon_{0})^{k+1}$ bound is only non-trivial
when $\varepsilon_{0}<1/n$. As discussed in the introduction, the seed length
of [BRRY14] is not better than Nisan’s PRG in this parameter regime.
Therefore, in the regular setting, even if we can take the base PRG to be the
improved PRG in [BRRY14], we do not get a better WPRG directly. The main
contribution of this work is to give an improved analysis of the error of
$\mathbf{M}_{0..n}^{(k)}$ in the regular setting.

###  2.3 Proof overview

Similar to [CHLTW23], the reason why we can get an improvement in the regular
setting is because a regular ROBP has a bounded “total amount of mixing”, no
matter how large $n$ is. Our goal is to inductively prove an approximation
guarantee that the error of $\mathbf{M}_{\ell..r}^{(k)}$ is _proportional to
the amount of mixing_ from layer $\ell$ to layer $r$. For the proof of WPRG
construction (Theorem 1.8), this statement is formalized based on the “weight”
defined in [BRRY14]. For the proof of non-black-box derandomization (Theorem
1.7), this statement is formalized with SV approximation [APPSV23]. We defer
the formal definitions to later sections, and focus on why this statement
gives a better bound.

The first observation is that the last two error terms in Lemma 2.1 combine
nicely. That is, by induction hypothesis we can show that the second last
error term $\mathbf{\Delta}_{\ell..m}^{(k)}\mathbf{M}_{m..r}$ is proportional
to the amount of mixing from layer $\ell$ to layer $m$, and the last error
term $\mathbf{M}_{\ell..m}\mathbf{\Delta}_{m..r}^{(k)}$ is proportional to the
amount of mixing from layer $m$ to layer $r$. Therefore, their sum is
proportional to the total amount of mixing from layer $\ell$ to layer $r$.
Furthermore, we observe that with a proper choice of parameters, the error
terms in the first two summations are actually very small compared to the last
two terms, and hence do not affect the total error too much.

Specifically, suppose we want to prove by induction that the error
$\mathbf{\Delta}_{\ell..r}^{(i)}$ is roughly bounded by the “level-$i$ error”
$\varepsilon^{(i)}$. We properly choose $\varepsilon^{(i)}$ as in the
following lemma, so that the error terms in the first two summations sum up to
roughly $\varepsilon^{(k)}/\log(n)$. We defer the proof to Appendix A.333One
can also choose $\varepsilon^{(i)}=\gamma^{i+1}/((2K+1)\log(n))$ where $K$ is
an upper bound for $k$. Then the proof of Lemma 2.2 becomes straightforward,
and it turns out that this does not affect the final result.

######  Lemma 2.2.

Let $\gamma<1/2$, and define
$\varepsilon^{(i)}=\frac{(\gamma)^{i+1}}{10\log(n)(i+1)^{2}}$. Then for every
$k\in\mathbb{N}$ we have

$\sum_{i+j=k}\varepsilon^{(i)}\varepsilon^{(j)}+\sum_{i+j=k-1}\varepsilon^{(i)}\varepsilon^{(j)}\leq\varepsilon^{(k)}/\log(n).$

With the choice of parameters above, we can prove that the error of the
“level-$k$ approximation” $\mathbf{M}_{\ell..r}^{(k)}$ only grows by a factor
of $(1+1/\log(n))$ after each recursion. After $\log(n)$ levels of recursion,
the error only grows by a constant factor. Therefore, we can choose the “base-
case error” $\varepsilon^{(0)}$ to be as small as $O(1/\log(n))$. This allows
us to choose base cases with small seed length or space complexity. For the
proof of Theorem 1.8, we choose the base case to be the [BRRY14] PRG with
error $2^{-\sqrt{\log(1/\varepsilon)}}$. For the proof of Theorem 1.7 the base
cases are generated using derandomized squaring [RV05, APPSV23].

###  2.4 Small-space computation

Finally, before we start the formal proofs, we briefly discuss the model of
space-bounded computation. We consider the standard model which is a Turing
machine with a read-only input tape, a constant number of work tapes, and a
write-only output tape. We say an algorithm runs in space $s$ if it uses at
most $s$ cells on the _work tapes_ throughout the computation. Note that the
input length and output length can be larger than $s$.

Next we recall some basic facts that we will use in space complexity analysis.
For parallel composition of algorithms
$\mathcal{A}_{1},\ldots,\mathcal{A}_{t}$ we can reuse the work tape and get
the following lemma.

######  Lemma 2.3.

Let $\mathcal{A}_{1},\ldots,\mathcal{A}_{t}$ be algorithms that on input $x$
run in space $s_{1},\ldots,s_{t}$ respectively. Then there exists an algorithm
$\mathcal{A}$ that on input $x$ outputs
$(\mathcal{A}_{1}(x),\mathcal{A}_{2}(x),\ldots,\mathcal{A}_{t}(x))$ and runs
in space $\max_{i\in[t]}(s_{i})+O(\log(t))$.

Furthermore, for sequential composition $\mathcal{A}_{1}(\mathcal{A}_{2}(x))$,
while we cannot fully store $\mathcal{A}_{2}(x)$ in the work tape, we can
still simulate an input tape containing $\mathcal{A}_{2}(x)$ by computing the
mapping $(x,i)\overset{}{\rightarrow}\mathcal{A}_{2}(x)_{[i]}$ instead. (See,
e.g., [AB09, Lemma 4.15].) This implies the following lemma.

######  Lemma 2.4.

Let $\mathcal{A}_{2}$ be an algorithm that runs in space $s_{2}$ on input $x$,
and $\mathcal{A}_{1}$ be an algorithm that runs in space $s_{1}$ on input
$\mathcal{A}_{2}(x)$. Then there exists an algorithm $\mathcal{A}$ that on
input $x$ outputs $\mathcal{A}_{1}(\mathcal{A}_{2}(x))$ in space
$s_{1}+s_{2}+O(\log(s_{1}+s_{2}+|\mathcal{A}_{2}(x)|))$.

We also use the following lemma that can be found in [MRSV17, AKMPSV20].

######  Lemma 2.5.

Let $\mathbf{M}_{1},\ldots,\mathbf{M}_{t}$ be $w\times w$ real matrices where
each entry has bit length at most $T$. Then $\prod_{i=1}^{t}\mathbf{M}_{i}$
can be computed in space $O(\log(t)\log(twT))$.

##  3 WPRG for regular ROBPs

Using the matrix notation, the weight defined in [BRRY14] can be written as
follows.444The original results in [BRRY14] only consider $y\in[0,1]^{w}$, but
one can easily generalize them to $\mathbb{R}^{w}$ by shifting and scaling.

######  Definition 3.1.

For every vector $y\in\mathbb{R}^{w}$ and every $i\in[n]$, define the _layer-
$i$ weight on $y$_ as

$W(i,y):=\sum_{u\in[w]}\sum_{b\in\\{0,1\\}}\left|(\mathbf{M}_{i}y)[u]-y[B_{i}(u,b)]\right|.$

For every $0\leq\ell<r\leq n$, the total weight between layer $\ell$ and $r$
on $y$ is defined as

$W(\ell,r,y):=\sum_{i=\ell+1}^{r}W(i,\mathbf{M}_{i..r}y).$

######  Remark 3.2.

To interpret $W(\ell,r,y)$ with the original description in [BRRY14], consider
the graph view of ROBPs, and consider $y$ to be the values on the nodes in
layer $r$. Then for every $i\leq r$, $\mathbf{M}_{i..r}y$ corresponds to the
values on layer $i$. Observe that each term in the definition of
$W(i,\mathbf{M}_{i..r}y)$ corresponds to the “weight” on an edge between layer
$i-1$ and $i$. In consequence, $W(\ell,r,y)$ corresponds to the total weight
of the _sub-program between layer $\ell$ and $r$_ (i.e. the ROBP specified by
transition functions $(B_{\ell+1},\ldots,B_{r})$).

The following identity is straightforward by definition:

######  Fact 2.

For every $0\leq\ell<m<r\leq n$ and every vector $y\in\mathbb{R}^{w}$,
$W(\ell,r,y)=W(\ell,m,\mathbf{M}_{m..r}y)+W(m,r,y)$. This also implies
$\max(W(\ell,m,\mathbf{M}_{m..r}y),W(m,r,y))\leq W(\ell,r,y)$.

Given the definition of weight, the main results in [BRRY14] imply the
following lemmas.666To get Lemma 3.4, we use the fact that
$\mathbf{M}_{\ell..r}(\cdot)$ corresponds to the transition matrices of a ROBP
of length $(r-\ell)$ and width $w$, and one can extend it to length $n$ by
adding more identity transitions which do not affect the total weight.

######  Lemma 3.3.

For every $\ell<r$ and every vector $y\in\mathbb{R}^{w}$, $W(\ell,r,y)\leq
w^{2}\left\|y\right\|_{\infty}$.

######  Lemma 3.4.

For every $\delta,W^{*}>0$, there exists an explicit PRG
$G_{0}:\\{0,1\\}^{d_{0}}\overset{}{\rightarrow}\\{0,1\\}^{n}$ s.t. for every
$0\leq\ell<r\leq n$,

$\left\|\left(\operatorname*{\mathbb{E}}_{s\sim\\{0,1\\}^{d_{0}}}\left[\mathbf{M}_{\ell..r}(G_{0}(s)_{[\leq
r-\ell]})\right]-\mathbf{M}_{\ell..r}\right)y\right\|_{\infty}\leq\delta
W(\ell,r,y).$

In addition, the seed length is
$d_{0}=O\left(\log(n)\left(\log\log(n)+\log(w/\delta)\right)\right)$.

Now define $W^{*}:=w^{2}$, which by Lemma 3.3 implies
$W^{*}\geq\max_{y:\left\|y\right\|_{\infty}=1}\left(W(0,n,y)\right)$. To
simplify notation, we define _weight approximation_ as follows.

######  Definition 3.5.

For every $0\leq\ell<r\leq n$, we say $\widetilde{\mathbf{M}_{\ell..r}}$ is a
$\varepsilon_{0}$-weight approximation of $\mathbf{M}_{\ell..r}$ if

$\left\|\left(\widetilde{\mathbf{M}_{\ell..r}}-\mathbf{M}_{\ell.r}\right)y\right\|_{\infty}\leq\varepsilon_{0}\cdot\frac{W(\ell,r,y)}{W^{*}}.$

Note that $\widetilde{\mathbf{M}_{\ell..r}}$ being a $\delta$-weight
approximation of $\mathbf{M}_{\ell..r}$ also implies
$\left\|\widetilde{\mathbf{M}_{\ell..r}}-\mathbf{M}_{\ell..r}\right\|_{\infty}\leq\delta$.
Now fix a parameter $\gamma>0$ to be specified later, and define
$\varepsilon^{(i)}=\frac{\gamma^{i+1}}{10(i+1)^{2}\log(n)}$ as in Lemma 2.2.
Let $G_{0}$ be the PRG in Lemma 3.4 with parameter
$\delta=\varepsilon^{(0)}/(3W^{*})$, and for every
$(\ell,r)\in\mathsf{BS}_{n}$ such that $r-\ell>1$, define

$\mathbf{M}_{\ell..r}^{(0)}:=\operatorname*{\mathbb{E}}_{s\sim\\{0,1\\}^{d_{0}}}\left[\mathbf{M}_{\ell..r}(G_{0}(s)_{[\leq
r-\ell]})\right],$

which is a $(\varepsilon^{(0)}/3)$-weight approximation by Lemma 3.4. Then
define $\mathbf{M}_{\ell..r}^{(k)}$ recursively as in Equation 1. The
following is our main lemma for proving Theorem 1.8:

######  Lemma 3.6 (main).

For every $k\in\mathbb{N}$, every $y\in\mathbb{R}^{w}$ and every
$(\ell,r)\in\mathsf{BS}_{n}$, $\mathbf{M}_{\ell..r}^{(k)}$ is a
$C_{t}\varepsilon^{(k)}$-weight approximation of $\mathbf{M}_{\ell..r}$, where
$t=\log(r-\ell)$ and $C_{t}=(1+1/\log(n))^{t}/3$.

###### Proof.

We prove the lemma by induction over $t$ and $k$. The first base case $t=0$ is
trivial since $\mathbf{M}_{\ell..r}^{(k)}=\mathbf{M}_{\ell..r}$. The second
base case $k=0$ is also true by definition. For the general case, first we
note that the lemma also implies
$\left\|\mathbf{\Delta}_{\ell.r}^{(k)}\right\|_{\infty}\leq
C_{t}\varepsilon^{(k)}\leq\varepsilon^{(k)}$. Then observe that by Lemma 2.1
and sub-additivity/sub-multiplicativity of infinity norm, we have

$\displaystyle\left\|\mathbf{\Delta}_{\ell..r}^{(k)}y\right\|_{\infty}\leq$
$\displaystyle\sum_{i+j\in\\{k-1,k\\}}\left\|\mathbf{\Delta}_{\ell..m}^{(i)}\mathbf{\Delta}_{m..r}^{(j)}y\right\|_{\infty}+\left\|\mathbf{M}_{\ell..m}\mathbf{\Delta}_{m..r}^{(k)}y\right\|_{\infty}+\left\|\mathbf{\Delta}_{\ell..m}^{(k)}\mathbf{M}_{m..r}y\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\sum_{i+j\in\\{k-1,k\\}}\left\|\mathbf{\Delta}_{\ell..m}^{(i)}\right\|_{\infty}\left\|\mathbf{\Delta}_{m..r}^{(j)}y\right\|_{\infty}+\left\|\mathbf{M}_{\ell..m}\right\|_{\infty}\left\|\mathbf{\Delta}_{m..r}^{(k)}y\right\|_{\infty}+\left\|\mathbf{\Delta}_{\ell..m}^{(k)}\mathbf{M}_{m..r}y\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\sum_{i+j\in\\{k-1,k\\}}\left(C_{t-1}^{2}\varepsilon^{(i)}\varepsilon^{(j)}\cdot\frac{W(m,r,y)}{W^{*}}\right)+C_{t-1}\varepsilon^{(k)}\cdot\frac{W(m,r,y)+W(\ell,m,\mathbf{M}_{m..r}y)}{W^{*}}\text{\phantom{(induction)}}$
(induction) $\displaystyle\leq$
$\displaystyle\,\,C_{t}\varepsilon^{(k)}\cdot\frac{W(\ell,r,y)}{W^{*}}.\text{\phantom{(by
\lx@cref{creftypecap~refnum}{lemma:error} and
\lx@cref{creftypecap~refnum}{lemma:weight})}}.$ (by Lemma 2.2 and 2)

In other words, $\mathbf{M}_{\ell..r}^{(k)}$ is a
$C_{t}\varepsilon^{(k)}$-weight approximation of $\mathbf{M}_{\ell..r}$. ∎

Lemma 3.6 shows that $\mathbf{M}_{0..n}^{(k)}$ is a $\varepsilon^{(k)}$-weight
approximation, which also implies
$\left\|\mathbf{M}_{0..n}^{(k)}-\mathbf{M}_{0..n}\right\|_{\infty}\leq\varepsilon^{(k)}$.
It remains to construct a WPRG that actually “implements”
$\mathbf{M}_{0..n}^{(k)}$. This step is rather standard and is essentially the
same as the corresponding step in [CHLTW23]: to get the seed length as claimed
in Theorem 1.8, we need to further “derandomize” $\mathbf{M}_{0..n}^{(k)}$
using the technique in [CDRST21, PV21]. In short, we expand the recursive
formula for $\mathbf{M}_{0..n}^{(k)}$ and get an “error reduction polynomial”
over matrices $\mathbf{M}_{i..j}^{(0)}$. One can show that there are at most
$K=n^{O(k)}$ terms in the polynomial, and each term has at most $h=k\log(n)$
factors. Then we can use the INW generator [INW94] for length $h$ and width
$w$ to approximate each term with error $\varepsilon/2K$, which gives us a
$\varepsilon/2$-approximation to $\mathbf{M}_{0..n}^{(k)}$. We discuss the
details in Section 3.1.

######  Remark 3.7.

Note that our construction and proof also works for “small-weight ROBPs” in
general, if we define
$W^{*}=\max_{B,y:\left\|y\right\|_{\infty}=1}\left(W(0,n,y)\right)$ instead.
Similar to [CHLTW23], this only costs additional $O(\log(n)\log(W^{*}))$ bits
of seed length.

###  3.1 Final WPRG construction

To simplify notation, we assume without loss of generality that the first
output bit of $G_{0}$ is unbiased, i.e.
$\Pr_{s\in\\{0,1\\}^{d_{0}}}\left[G_{0}(d_{0})_{[1]}=1\right]=1/2$.777To get
such a PRG, we can simply take a PRG $G_{0}^{\prime}$ from [BRRY14] with
$(n-1)$-bit output and define $G_{0}(b\circ s)=b\circ G_{0}^{\prime}(s)$,
where $b$ is the first bit. Then we can merge the two different base cases by
defining
$\mathbf{M}^{(0)}_{r-1..r}:=\mathbf{M}_{r}=\mathbf{M}_{r-1..r}^{(k)}=\operatorname*{\mathbb{E}}_{s\in\\{0,1\\}^{d_{0}}}\left[\mathbf{M}_{r-1..r}(G_{0}(s)_{[\leq
1]})\right]$. Now consider the following notation.

######  Definition 3.8.

For every $0\leq\ell<r\leq n$, let $\mathsf{IS}_{\ell..r}$ denote the set of
increasing sequences $\mathsf{sq}=(i_{0},i_{1}\ldots,i_{h})$ s.t.
$\ell=i_{0}<i_{1}<\ldots<i_{h}=r$. We say $h$ is the _length_ of $\mathsf{s}$.
For every $\mathsf{sq}\in\mathsf{IS}_{\ell..r}$, define

$\mathbf{M}^{(0)}_{\mathsf{sq}}:=\prod_{j=1}^{h}\mathbf{M}^{(0)}_{i_{j-1}..i_{j}}.$

Given the notation above, we get the following lemma regarding the expansion
of $\mathbf{M}_{0..n}^{(k)}$, which is not hard to prove by induction. For
completeness we include a proof in Appendix B.

######  Lemma 3.9.

For every $k\in\mathbb{N}$ and every $(\ell,r)\in\mathsf{BS}_{n}$, there is a
(multi)set $S\subseteq\mathsf{IS}_{\ell..r}\times\\{-1,+1\\}$ which satisfies
that

  * •

$\mathbf{M}_{\ell..r}^{(k)}=\sum_{(\mathsf{sq},\sigma)\in
S}\sigma\mathbf{M}_{\mathsf{sq}}^{(0)}.$

  * •

$|S|\leq(r-\ell)^{2k}$

  * •

For every $(\mathsf{sq},\sigma)\in S$, the length of $\mathsf{sq}$ is at most
$k\log(r-\ell)+1$

In addition, we would need to derandomize each term
$\mathbf{M}_{\mathsf{sq}}^{(0)}$ using the following matrix view of INW
generator [INW94], which can be found in, e.g., [BCG20]:

######  Lemma 3.10.

Let $\Sigma$ be a finite set of symbols. Suppose for every $i\in[h]$, there is
a matrix-valued function
$\mathbf{A}_{i}:\Sigma\overset{}{\rightarrow}\mathbb{R}^{w\times w}$ which on
every input in $\Sigma$ outputs a stochastic matrix. Then for every
$\varepsilon_{\mathrm{INW}}>0$ there exists an explicit function
$G_{\mathrm{INW}}:\\{0,1\\}^{d}\overset{}{\rightarrow}\Sigma^{h}$ such that

$\left\|\operatorname*{\mathbb{E}}_{s\in\\{0,1\\}^{d}}\left[\prod_{i=1}^{h}{\mathbf{A}_{i}(G_{\mathrm{INW}}(s)_{[i]})}\right]-\prod_{i=1}^{h}\operatorname*{\mathbb{E}}_{x\in\Sigma}\left[\mathbf{A}_{i}(x)\right]\right\|_{\infty}\leq\varepsilon_{\mathrm{INW}},$

and $d=O(\log\left|\Sigma\right|+\log(h)\log(hw/\varepsilon_{\mathrm{INW}}))$.

Now we are ready to prove Theorem 1.8.

###### Proof of Theorem 1.8.

Let $S\subseteq\mathsf{IS}_{0..n}\times[-1,1]$ be the set defined in Lemma 3.9
s.t. $\mathbf{M}_{0..n}^{(k)}=\sum_{(\mathsf{sq},\sigma)\in
S}\sigma\mathbf{M}_{\mathsf{sq}}^{(0)}$. Without loss of generality we can
assume that $S$ has size exactly $2^{2k\log(n)}$ by adding dummy sequences
with weight $\sigma=0$. In addition, note that there is a enumeration function
$E_{S}:\\{0,1\\}^{2k\log(n)}\overset{}{\rightarrow}S$ that can be implemented
in space $O(\log(k)\log(n))$ following recursive formula (1).888That is, we
use the first $\lceil\log(2k+1)\rceil$ bits as index to determine a term in
the recursive formula, then discard these $\lceil\log(2k+1)\rceil$ bits and
recurse. If there’s any undefined index, simply return a dummy sequence with
weight $0$. Then consider
$G_{\mathrm{INW}}:\\{0,1\\}^{d_{\mathrm{INW}}}\overset{}{\rightarrow}\Sigma^{h}$
in Lemma 3.10 with $\Sigma=\\{0,1\\}^{d_{0}},h=k\log(n)+1$ and
$\varepsilon_{\mathrm{INW}}=\varepsilon/(2|S|)$, then define
$d=2k\log(n)+d_{\mathrm{INW}}$. The final WPRG construction
$(\rho,G):\\{0,1\\}^{d}\overset{}{\rightarrow}\mathbb{R}\times\\{0,1\\}^{n}$
is as follows. On any input $s$,

  1. 1.

Parse $s$ as
$(s_{\mathrm{enum}},s_{\mathrm{INW}})\in\\{0,1\\}^{2k\log(n)}\times\\{0,1\\}^{d_{\mathrm{INW}}}$

  2. 2.

Define $((i_{0},i_{1},\ldots,i_{h}),\sigma):=E_{S}(s_{\mathrm{enum}})$.

  3. 3.

For $j\in[h]$, define
$r_{j}:=G_{0}(G_{\mathrm{INW}}(y)_{[j]})\in\\{0,1\\}^{n}$.

  4. 4.

Output $(\rho(s),G(s)):=(\sigma|S|,(r_{1})_{[\leq
i_{1}-i_{0}]}\circ(r_{2})_{[\leq i_{2}-i_{1}]}\circ\ldots\circ(r_{h})_{[\leq
i_{h}-i_{h-1}]})$.

Next we prove the correctness of $G$. Observe that

$\operatorname*{\mathbb{E}}_{s}\left[\rho(s)\mathbf{M}_{0..n}(G(s))\right]=\sum_{((i_{0},\ldots,i_{h}),\sigma)\in
S}\sigma\cdot\operatorname*{\mathbb{E}}_{s_{INW}}\left[\prod_{j=1}^{h}\mathbf{M}_{i_{j-1}..i_{j}}(G_{0}(G_{\mathrm{INW}}(s_{\mathrm{INW}})_{[j]}))\right].$

For every term in the above equation, consider the matrix-valued functions
$\mathbf{A}_{j}:\\{0,1\\}^{d_{0}}\overset{}{\rightarrow}\mathbb{R}^{w\times
w}$ s.t. $\mathbf{A}_{j}(r)=\mathbf{M}_{i_{j-1}..i_{j}}(G_{0}(r)_{[\leq
i_{j}-i_{j-1}]})$. Note that
$\operatorname*{\mathbb{E}}_{r}\left[\mathbf{A}_{j}(r)\right]=\mathbf{M}_{i_{j-1}..i_{j}}^{(0)}$.
Then by Lemma 3.10 we have

$\left\|\operatorname*{\mathbb{E}}_{s_{INW}}\left[\prod_{j=1}^{h}\mathbf{M}_{i_{j-1}..i_{j}}(G_{\mathrm{INW}}(s_{\mathrm{INW}})_{j})\right]-\mathbf{M}_{(i_{0},i_{1},\ldots,i_{h})}^{(0)}\right\|_{\infty}\leq\varepsilon/(2|S|),$

which by the sub-additivity of $\left\|\cdot\right\|_{\infty}$ implies

$\left\|\operatorname*{\mathbb{E}}_{s}\left[\rho(s)\mathbf{M}_{0..n}(G(s))\right]-\mathbf{M}_{0..n}^{(k)}\right\|_{\infty}\leq\varepsilon/2.$

We pick suitable $\gamma,k$ (to be specified later) so that
$\varepsilon^{(k)}\leq\varepsilon/2$. Then by Lemma 3.6 we have

$\left\|\operatorname*{\mathbb{E}}_{s}\left[\rho(s)\mathbf{M}_{0..n}(G(s))\right]-\mathbf{M}_{0..n}^{(k)}\right\|_{\infty}\leq\varepsilon.$

Then consider the vectors $v_{\mathsf{st}},v_{\mathsf{ed}}\in\mathbb{R}^{w}$
corresponding to the start and end states as discussed in Section 2. Observe
that $\left\|v_{\mathsf{st}}\right\|_{1}=1$ and
$\left\|v_{\mathsf{ed}}\right\|_{\infty}\leq 1$ by definition. Therefore we
have

$\displaystyle\left|\operatorname*{\mathbb{E}}_{s\in\\{0,1\\}^{d}}\left[\rho(s)B(G(s))\right]-\operatorname*{\mathbb{E}}_{x\in\\{0,1\\}^{n}}\left[B(x)\right]\right|$
$\displaystyle=\left|v_{\mathsf{st}}^{\top}\left(\operatorname*{\mathbb{E}}_{s}\left[\rho(s)\mathbf{M}_{0..n}(G(s))\right]-\operatorname*{\mathbb{E}}_{x}\left[\mathbf{M}_{0..n}(x)\right]\right)v_{\mathsf{ed}}\right|$
$\displaystyle\leq\left\|v_{\mathsf{st}}\right\|_{1}\cdot\left\|\operatorname*{\mathbb{E}}_{s}\left[\rho(s)\mathbf{M}_{0..n}(G(s))\right]-\mathbf{M}_{0..n}\right\|_{\infty}\cdot\left\|v_{\mathsf{ed}}\right\|_{\infty}$
$\displaystyle\leq\varepsilon.$

Finally we analyze the seed length with an unspecified parameter
$0<\gamma<1/\log(n)$. Take $k$ to be the minimum integer s.t.
$\varepsilon^{(k)}\leq\varepsilon/2$. Observe that
$\log(1/\varepsilon^{(0)})=O(1/\gamma)$ and
$k=O(\log(1/\varepsilon)/\log(1/\gamma))$. This implies

$d=d_{0}+O(\log(h)\log(hw/\varepsilon)+k\log(n))=d_{0}+\tilde{O}(\log(w/\varepsilon)+k\log(n)).$

By Lemma 3.4, we have

$d_{0}=O(\log(n)\log(wW^{*}/\gamma)+\log(n)\log\log(n))=\tilde{O}(\log(n)\log(w/\gamma)).$

Therefore,

$d=\tilde{O}\left(\log(n)\log(w/\gamma)+\frac{\log(n)\log(1/\varepsilon)}{\log(1/\gamma)}+\log(1/\varepsilon)\right).$

Taking $\gamma=2^{-\sqrt{\log(n)}}$, we get

$d=\tilde{O}\left(\log(n)\left(\log(w)+\sqrt{\log(1/\varepsilon)}\right)+\log(1/\varepsilon)\right).$

Finally, observe that the space complexity is
$O(d_{0}+\log(k)\log(n)+d_{\mathrm{INW}})=O(d)$. Therefore the WPRG is
explicit. ∎

##  4 Non-black-box Derandomization for Regular ROBPs

We prove Theorem 1.7 in this section. Inspired by [CHLTW23], we use the notion
of SV approximation to capture the “amount of mixing”. To simplify notation,
we define the function $D:\mathbb{R}^{w\times
w}\times\mathbb{R}^{w}\overset{}{\rightarrow}\mathbb{R}$ to be
$D(\mathbf{A},y):=\left\|y\right\|^{2}-\left\|\mathbf{A}y\right\|^{2}$, which
plays the same role as the weight measure in the proof of Theorem 1.8. The
following fact is straightforward from the definition.

######  Fact 3.

$D(\mathbf{B},y)+D(\mathbf{A},\mathbf{B}y)=D(\mathbf{A}\mathbf{B},y)$.

The notion of singular value approximation (SV approximation) is defined as
follows.

######  Definition 4.1 (SV approximation [APPSV23]).

Let $\mathbf{W}\in\mathbb{R}^{w\times w}$ be a doubly stochastic matrix. We
say $\widetilde{\mathbf{W}}$ is a $\varepsilon$-SV approximation of $W$ if for
every $x,y\in\mathbb{R}^{w}$,

$\left|x^{\top}(\widetilde{\mathbf{W}}-\mathbf{W})y\right|\leq\varepsilon\cdot\left(\frac{D(\mathbf{W}^{\top},x)+D(\mathbf{W},y)}{2}\right).$

Equivalently, for every $x,y\in\mathbb{R}^{w}$,

$\left|x^{\top}(\widetilde{\mathbf{W}}-\mathbf{W})y\right|\leq\varepsilon\cdot\left(\sqrt{D(\mathbf{W}^{\top},x)\cdot
D(\mathbf{W},y)}\right).$

The proof of Theorem 1.7 is very similar to our proof of Theorem 1.8 in the
previous section. First we also need a base case for the different
approximation notion. As proved in [APPSV23, CHLTW23], there is a space-
efficient implementation of SV approximation of random walk matrices based on
derandomized squaring [RV05]:

######  Lemma 4.2 ([APPSV23, CHLTW23]).

For every $(\ell,r)\in\mathsf{BS}_{n}$, there is an algorithm that computes a
$\delta$-SV approximation of $\mathbf{M}_{\ell..r}$ in space
$\tilde{O}(\log(nw)\log(1/\delta))$. Further, each entry of this approximation
matrix has bit length at most $O(\log(n)\log(1/\delta))$.

We also need the following simple lemma, which can be found in [CHLTW23]. We
include its (short) proof for completeness.

######  Lemma 4.3.

Suppose $\widetilde{\mathbf{W}}$ is a $\delta$-SV-approximation of
$\mathbf{W}$, and let $\mathbf{\Delta}=\widetilde{\mathbf{W}}-\mathbf{W}$.
Then

$\left\|\mathbf{\Delta}y\right\|_{2}\leq\delta\sqrt{D(\mathbf{W},y)}.$

###### Proof.

Observe that

$\left\|\mathbf{\Delta}y\right\|_{2}^{2}=(\mathbf{\Delta}y)^{\top}\mathbf{\Delta}y\leq\delta\sqrt{D(\mathbf{W},y)\cdot(\left\|\mathbf{\Delta}y\right\|_{2}^{2}-\left\|\mathbf{W}^{\top}\mathbf{\Delta}y\right\|_{2}^{2})}\leq\delta\sqrt{D(\mathbf{W},y)}\cdot\left\|\mathbf{\Delta}y\right\|.$

∎

Now for every $(\ell,r)\in\mathsf{BS}_{n}$, define
$\mathbf{M}_{\ell..r}^{(0)}$ to be a $(\varepsilon^{(0)}/3)$-SV approximation
of $\mathbf{M}_{\ell..r}$, and define $\mathbf{M}_{\ell..r}^{(k)}$ using the
recursion (Equation 1). We prove the following lemma which is analogous to
Lemma 3.6:

######  Lemma 4.4 (main).

For every $k\in\mathbb{N}$ and every $(\ell,r)\in\mathsf{BS}_{n}$,
$\mathbf{M}_{\ell..r}^{(k)}$ is a $C_{t}\varepsilon^{(k)}$-SV approximation of
$\mathbf{M}_{\ell..r}$, where $t=\log(r-\ell)$ and
$C_{t}=(1+1/\log(n))^{t}/3$.

###### Proof.

We again prove the lemma by induction. The base cases $t=0$ or $k=0$ are
trivial by definition. For the general case, observe that by Lemma 2.1, for
every $x,y\in\mathbb{R}^{w}$ we have

$x^{\top}\mathbf{\Delta}_{\ell..r}^{(k)}y=\sum_{i+j=k}x^{\top}\mathbf{\Delta}_{\ell..m}^{(i)}\mathbf{\Delta}_{m..r}^{(j)}y-\sum_{i+j=k-1}x^{\top}\mathbf{\Delta}_{\ell..m}^{(i)}\mathbf{\Delta}_{m..r}^{(j)}y+x^{\top}\mathbf{M}_{\ell..m}\mathbf{\Delta}_{m..r}^{(k)}y+x^{\top}\mathbf{\Delta}_{\ell..m}^{(k)}\mathbf{M}_{m..r}y.$
(2)

To bound the first two summations in Equation 2, observe that

$\displaystyle\sum_{i+j=k}x^{\top}\mathbf{\Delta}_{\ell..m}^{(i)}\mathbf{\Delta}_{m..r}^{(j)}y-\sum_{i+j=k-1}x^{\top}\mathbf{\Delta}_{\ell..m}^{(i)}\mathbf{\Delta}_{m..r}^{(j)}y$
$\displaystyle\leq\sum_{i+j\in\\{k-1,k\\}}\left\|(\mathbf{\Delta}^{(i)}_{\ell..m})^{\top}x\right\|_{2}\left\|\mathbf{\Delta}^{(j)}_{m..r}y\right\|_{2}\text{\phantom{(Cauchy-
Schwarz)}}$ (Cauchy-Schwarz) $\displaystyle\leq
C_{t-1}^{2}\sum_{i+j\in\\{k-1,k\\}}\varepsilon^{(i)}\varepsilon^{(j)}\sqrt{D\left(\mathbf{M}_{\ell..m}^{\top},x\right)D\left(\mathbf{M}_{m..r},y\right)}\text{\phantom{(\lx@cref{creftypecap~refnum}{lemma:SV-
norm})}}$ (Lemma 4.3) $\displaystyle\leq
C_{t-1}^{2}\cdot\frac{\varepsilon^{(k)}}{\log(n)}\cdot\frac{D\left(\mathbf{M}_{\ell..m}^{\top},x\right)+D\left(\mathbf{M}_{m..r},y\right)}{2}\text{\phantom{(by
\lx@cref{creftypecap~refnum}{lemma:error} and AM-GM)}}$ (by Lemma 2.2 and AM-
GM) $\displaystyle\leq
C_{t-1}\cdot\frac{\varepsilon^{(k)}}{\log(n)}\cdot\frac{D\left(\mathbf{M}_{\ell..r}^{\top},x\right)+D\left(\mathbf{M}_{\ell..r},y\right)}{2}\text{\phantom{(since
$C_{t-1}\leq 1$ and
$\left\|\mathbf{M}_{\ell..m}\right\|_{2},\left\|\mathbf{M}_{m..r}^{\top}\right\|_{2}\leq
1$)}}$ (since $C_{t-1}\leq 1$ and
$\left\|\mathbf{M}_{\ell..m}\right\|_{2},\left\|\mathbf{M}_{m..r}^{\top}\right\|_{2}\leq
1$)

To bound the last two terms in Equation 2, observe that

$\displaystyle
x^{\top}\mathbf{M}_{\ell..m}\mathbf{\Delta}_{m..r}^{(k)}y+x^{\top}\mathbf{\Delta}_{\ell..m}^{(k)}\mathbf{M}_{m..r}y$
$\displaystyle\leq
C_{t-1}\cdot\varepsilon^{(k)}\cdot\frac{D(\mathbf{M}_{m..r},y)+D(\mathbf{M}_{m..r}^{\top},\mathbf{M}_{\ell..m}^{\top}x)+D(\mathbf{M}_{\ell..m},\mathbf{M}_{m..r}y)+D(\mathbf{M}_{\ell..m}^{\top},x)}{2}$
$\displaystyle=C_{t-1}\cdot\varepsilon^{(k)}\cdot\frac{D(\mathbf{M}_{\ell..r},y)+D(\mathbf{M}_{\ell..r}^{\top},x)}{2}.\text{\phantom{(\lx@cref{creftypecap~refnum}{lemma:weight})}}$
(2)

By summing up the two inequalities, we can conclude that

$x^{\top}\mathbf{\Delta}_{\ell..r}^{(k)}y\leq
C_{t}\cdot\varepsilon^{(k)}\cdot\frac{D(\mathbf{M}_{\ell..r},y)+D(\mathbf{M}_{\ell..r}^{\top},x)}{2}.$

Because negating $y$ does not change the bound above, we get

$\left|x^{\top}(\mathbf{M}_{\ell..r}^{(k)}-\mathbf{M}_{\ell..r})y\right|\leq
C_{t}\cdot\varepsilon^{(k)}\cdot\frac{D(\mathbf{M}_{\ell..r},y)+D(\mathbf{M}_{\ell..r}^{\top},x)}{2},$

i.e. $\mathbf{M}_{\ell..r}^{(k)}$ is a $C_{t}\varepsilon^{(k)}$-SV
approximation of $\mathbf{M}_{\ell..r}$. ∎

Finally, let $\gamma=1/\log(n)$ and $k=O(\log(1/\varepsilon)/\log(1/\gamma))$
be the minimum integer s.t. $\varepsilon^{(k)}\leq\varepsilon$. We claim that
$\mathbf{M}_{0..n}^{(k)}$ can be implemented in space
$\tilde{O}(\log(k)\log(nw))$, which implies the following result:

######  Theorem 4.5.

There is an algorithm which can compute an $\varepsilon$-SV approximation of
the random walk matrix $\mathbf{M}_{0..n}$ in space
$\tilde{O}(\log(nw)\log\log(1/\varepsilon))$.

Note that Theorem 1.7 is also a direct corollary of this theorem:

###### Proof of Theorem 1.7.

Compute a $(\varepsilon/\sqrt{w})$-SV approximation of $\mathbf{M}_{0..n}$,
denoted by $\widetilde{\mathbf{M}_{0..n}}$. By Theorem 4.5 this takes space
$\tilde{O}(\log(nw)\log\log(1/\varepsilon))$. Then consider
$v_{\mathsf{st}},v_{\mathsf{ed}}$ as defined in Section 2, and output
$v_{\mathsf{st}}^{\top}\widetilde{\mathbf{M}_{0..n}}v_{\mathsf{ed}}$. To prove
the correctness, recall that
$v_{\mathsf{st}}^{\top}\mathbf{M}_{0..n}v_{\mathsf{ed}}=\operatorname*{\mathbb{E}}_{x}\left[B(x)\right]$,
which implies

$\displaystyle\left|v_{\mathsf{st}}^{\top}\widetilde{\mathbf{M}_{0..n}}v_{\mathsf{ed}}-\operatorname*{\mathbb{E}}_{x\in\\{0,1\\}^{n}}\left[B(x)\right]\right|=\left|v_{\mathsf{st}}^{\top}(\widetilde{\mathbf{M}_{0..n}}-\mathbf{M}_{0..n})v_{\mathsf{ed}}\right|\leq\varepsilon/\sqrt{w}\left\|v_{\mathsf{st}}\right\|\left\|v_{\mathsf{ed}}\right\|\leq\varepsilon$

by the fact that $\left\|v_{\mathsf{st}}\right\|=1$ and
$\left\|v_{\mathsf{ed}}\right\|\leq\sqrt{w}$. ∎

######  Remark 4.6.

Note that $\mathbf{M}_{0..n}^{(k)}$ does not satisfy the original definition
of SV approximation in [APPSV23] because it is not necessarily doubly
stochastic. While every row and column in $\mathbf{M}_{0..n}^{(k)}$ does sum
up to $1$, some of its entries might be negative.

###  4.1 Space-efficient implementation

Finally we prove that $\mathbf{M}_{0..n}^{(k)}$ can be implemented in space
$\tilde{O}(\log(k)\log(nw))$. Note that a naive implementation of the
recursion (Equation 1) takes at least $O(\log(n)\log(wk))$ space. Furthermore,
we cannot naively enumerate each term of $\mathbf{M}_{0..n}^{(k)}$ in its
expansion (Lemma 3.9) either, because there are $n^{O(k)}$ terms in total,
which takes at least $O(k\log(n))$ bits to enumerate.

To reduce the space complexity, we will compute $\mathbf{M}_{0..n}$ with a
different recursive formula. The intuition of the new recursion is as follows.
First observe that each term in the expansion of $\mathbf{M}_{0..n}^{(k)}$
corresponds to a way to put $k$ balls into $2n-1$ bins (indexed by $[2n-1]$),
under the constraint that each odd-indexed bin contains at most one ball. To
see why this is the case, observe that the original recursion corresponds to
the following way to recursively enumerate all the ball-to-bin combinations:
first we put $b\in\\{0,1\\}$ ball in the middle bin (which corresponds to the
sign $(-1)^{b}$), then choose $i,j$ s.t. $i+j=k-b$, and then recursively put
$i$ balls in the left $(n-1)$ bins (which corresponds to
$\mathbf{M}_{0..n/2}^{(i)}$) and $j$ balls in the right $(n-1)$ bins (which
corresponds to $\mathbf{M}_{n/2..n}^{(j)}$).

Then observe that there is a different way to enumerate all the combinations
with only $\lceil\log(k)\rceil$ levels of recursion as follows. First decide
where the $h$-th ball is located, where $h=\lceil k/2\rceil$. If it is in an
even-indexed bin, also decide how many balls are on the left and how many
balls are on the right. Otherwise, there can be only one ball in the selected
odd-indexed bin, and the numbers of balls on the left and right are fixed.
Then for each choice, recursively enumerate the combinations on the left and
right respectively. We claim that there is a corresponding recursive formula
for $\mathbf{M}_{0..n}^{(k)}$ which can be implemented in only
$\tilde{O}(\log(k)\log(nw))$ space.

To define this recursive formula, first we generalize the definition of
$\mathbf{M}_{\ell..r}^{(k)}$ to $(\ell,r)\not\in\mathsf{BS}_{n}$. For any
$(\ell,r)$ s.t. $0\leq\ell<r\leq n$, define $\mathsf{LCA}(\ell,r)$ as follows.
Let $t$ be the largest integer such that there exists a multiple of $2^{t}$ in
the range $(\ell,r)$. Then we define $\mathsf{LCA}(\ell,r)$ to be the unique
multiple of $2^{t}$ in $(\ell,r)$.999If there are two consecutive multiples of
$2^{t}$ in $(\ell,r)$, then $2^{t+1}$ divides one of them, which violates the
definition of $t$. Observe that for $(\ell,r)\in\mathsf{BS}_{n}$ s.t.
$r-\ell>1$, $\mathsf{LCA}(\ell,r)=(\ell+r)/2$. Therefore, we can generalize
the recursion (Equation 1) to any $r-\ell>1$ by defining
$m=\mathsf{LCA}(\ell,r)$. We also generalize the same recursion to
$k=0,(\ell,r)\not\in\mathsf{BS}_{n}$, so that
$\mathbf{M}_{\ell..r}^{(0)}=\mathbf{M}_{\ell..m}^{(0)}\mathbf{M}_{m..r}^{(0)}$.101010There
is an empty summation term $\sum_{i+j=-1}$ which should be treated as $0$. For
the degenerate case $\ell=r$ we define
$\mathbf{M}_{\ell..r}^{(k)}=\mathbf{I}_{w}$. Next we want to prove the
following identity which naturally gives a recursive algorithm for
$\mathbf{M}_{0..n}$. This identity is essentially the recursive enumeration we
described above, except that we utilize
$\mathbf{M}_{s-1..s}^{(k)}=\mathbf{M}_{s}$ to get some cancellation which
simplifies the recursion.

######  Lemma 4.7.

For every $(\ell,r)$ s.t. $r>\ell$ and every $h,k\in\mathbb{N}$ s.t. $h\leq
k$, we have the following identity:

$\mathbf{M}_{\ell..r}^{(k)}=\sum_{s=\ell+1}^{r}\mathbf{M}_{\ell..s-1}^{(h-1)}\mathbf{M}_{s}\mathbf{M}_{s..r}^{(k-h)}-\sum_{s=\ell+1}^{r-1}\mathbf{M}_{\ell..s}^{(h-1)}\mathbf{M}_{s..r}^{(k-h)}.$
(3)

Surprisingly, this new recursion coincides with the recursion of Richardson
iteration from the inverse Laplacian perspective. This shows that the
construction in [CHLTW23] is actually equivalent to the [CL20] construction
that we use in this paper. We briefly discuss this equivalence in Appendix D.

Before we prove the identity, we show that the new recursion does imply an
algorithm that runs in space $\tilde{O}(\log(k)\log(nw))$. Consider the
algorithm which recursively computes $\mathbf{M}_{\ell..r}^{(k)}$ using the
formula in Lemma 4.7 with $h=\lceil k/2\rceil$. Observe that the right hand
side of Equation 3 involves at most $O(n)$ matrices. In addition, given all
the matrices on the right hand side, the computation of
$\mathbf{M}_{\ell..r}^{(k)}$ takes only $O(\log(nkwT))$ additional bits, where
$T$ is the maximum bit length of all the matrix entries. From Lemma 3.9 and
Lemma 4.2 we can see that $T$ is at most $\tilde{O}(k\log^{2}(n))$, so
$O(\log(nwkT))=\tilde{O}(\log(nwk))$. Finally, observe that each matrix on the
right hand side has precision parameter at most $\max(h-1,k-h)\leq\lfloor
k/2\rfloor$. Therefore the recursion reaches the $\mathbf{M}_{\ell..r}^{(0)}$
base cases after at most $\lceil\log(k)\rceil$ levels. By repeatedly applying
Lemma 2.4 and Lemma 2.3 we can conclude that the space complexity is at most
$\tilde{O}(\log(k)\log(nw))+O(s_{\mathrm{base}})$, where $s_{\mathrm{base}}$
is the maximum space complexity of computing $\mathbf{M}_{\ell..r}^{(0)}$. The
base case complexity $s_{\mathrm{base}}$ is indeed $\tilde{O}(\log(nw))$,
which we prove in Appendix C.

Finally, we prove the identity in Lemma 4.7.

###### Proof of Lemma 4.7.

We prove the claim by induction on $r-\ell$. Let $m=\mathsf{LCA}(\ell,r)$. For
the base case $r-\ell=1$, the lemma says
$\mathbf{M}_{\ell..r}^{(k)}=\mathbf{M}_{\ell..\ell}^{(h-1)}\mathbf{M}_{r}{\mathbf{M}_{r..r}}$,
which is trivially true. Next we prove the general case by induction. For each
matrix $\mathbf{M}_{\ell^{\prime}..r^{\prime}}^{(k^{\prime})}$ on the right
hand side s.t. $\ell^{\prime}<m<r^{\prime}$, we expand
$\mathbf{M}_{\ell^{\prime}..r^{\prime}}^{(k^{\prime})}$ using (1). Note that
$\mathsf{LCA}(\ell^{\prime},r^{\prime})$ is also $m$. In addition, for the
$s=m$ term in the first summation we apply the dummy expansion
$\mathbf{M}^{(k-h)}_{m..r}=\sum_{a+b=k-h}\mathbf{M}_{m..m}^{(a)}\mathbf{M}_{m..r}^{(b)}-\sum_{a+b=k-h-1}\mathbf{M}_{m..m}^{(a)}\mathbf{M}_{m..r}^{(b)}$.
Similarly, for the $s=m+1$ term in the first summation we also expand
$\mathbf{M}^{(k-h)}_{\ell..m}=\sum_{a+b=h-1}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..m}^{(b)}-\sum_{a+b=h-2}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..m}^{(b)}$.
After rearranging we get that the right hand side equals to

$\displaystyle\sum_{s=\ell+1}^{m}\sum_{a+b=k-h}\mathbf{M}_{\ell..s-1}^{(h-1)}\mathbf{M}_{s}\mathbf{M}_{s..m}^{(a)}\mathbf{M}_{m..r}^{(b)}$
$\displaystyle-\sum_{s=\ell+1}^{m-1}\sum_{a+b=k-h}\mathbf{M}_{\ell..s}^{(h-1)}\mathbf{M}_{s..m}^{(a)}\mathbf{M}_{m..r}^{(b)}$
$\displaystyle-\sum_{s=\ell+1}^{m}\sum_{a+b=k-h-1}\mathbf{M}_{\ell..s-1}^{(h-1)}\mathbf{M}_{s}\mathbf{M}_{s..m}^{(a)}\mathbf{M}_{m..r}^{(b)}$
$\displaystyle+\sum_{s=\ell+1}^{m-1}\sum_{a+b=k-h-1}\mathbf{M}_{\ell..s}^{(h-1)}\mathbf{M}_{s..m}^{(a)}\mathbf{M}_{m..r}^{(b)}$
$\displaystyle+\sum_{s=m+1}^{r}\sum_{a+b=h-1}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..s-1}^{(b)}\mathbf{M}_{s}\mathbf{M}_{s..r}^{(k-h)}$
$\displaystyle-\sum_{s=m+1}^{r}\sum_{a+b=h-1}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..s}^{(b)}\mathbf{M}_{s..r}^{(k-h)}$
$\displaystyle-\sum_{s=m+1}^{r}\sum_{a+b=h-2}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..s-1}^{(b)}\mathbf{M}_{s}\mathbf{M}_{s..r}^{(k-h)}$
$\displaystyle+\sum_{s=m+1}^{r}\sum_{a+b=h-2}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..s}^{(b)}\mathbf{M}_{s..r}^{(k-h)}$
$\displaystyle-\mathbf{M}_{\ell..m}^{(h-1)}\mathbf{M}_{m..r}^{(k-h)}.$

Note that the first summation in Equation 3 expands to the terms on the left,
and the second summation in Equation 3 expands to the terms on the right.

Now we classify all the terms in the first line by $b$, and take out the right
factor $\mathbf{M}_{m..r}^{(b)}$. For any fixed $b\leq k-h$ we get the sum

$\left(\sum_{s=\ell+1}^{m}\mathbf{M}_{\ell..s-1}^{(h-1)}\mathbf{M}_{s}\mathbf{M}_{s..m}^{(k-b-h)}-\sum_{s=\ell+1}^{m-1}\mathbf{M}_{\ell..s}^{(h-1)}\mathbf{M}_{s..m}^{(k-b-h)}\right)\mathbf{M}_{m..r}^{(b)}.$

Observe that this is exactly
$\mathbf{M}_{\ell..m}^{(k-b)}\mathbf{M}_{m..r}^{(b)}$ by induction. Therefore,
we can see that the first line is exactly
$\sum_{b=0}^{k-h}\mathbf{M}_{\ell..m}^{(k-b)}\mathbf{M}_{m..r}^{(b)}$.
Similarly, we can get that the second line is
$-\sum_{b=0}^{k-h-1}\mathbf{M}_{\ell..m}^{(k-b-1)}\mathbf{M}_{m..r}^{(b)}$.
For the third and fourth lines, we can also classify the terms by $a$ and take
out the left factor $\mathbf{M}_{\ell..m}^{(a)}$ to get to get
$\sum_{a=0}^{h-1}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..r}^{(k-a)}$ and
$-\sum_{a=0}^{h-2}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..r}^{(k-a-1)}$
respectively. Finally, collect all the simplified terms (including the only
term in the fifth line in the expansion), and we get

$\displaystyle\sum_{b=0}^{k-h}\mathbf{M}_{\ell..m}^{(k-b)}\mathbf{M}_{m..r}^{(b)}+\sum_{a=0}^{h-1}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..r}^{(k-a)}-\sum_{b=0}^{k-h-1}\mathbf{M}_{\ell..m}^{(k-b)}\mathbf{M}_{m..r}^{(b)}-\sum_{a=0}^{h-2}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..r}^{(k-a-1)}-\mathbf{M}_{\ell..m}^{(h-1)}\mathbf{M}_{m..r}^{(k-h)}$
$\displaystyle=\sum_{a+b=k}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..r}^{(b)}-\sum_{a+b=k-1}\mathbf{M}_{\ell..m}^{(a)}\mathbf{M}_{m..r}^{(b)}$
$\displaystyle=\mathbf{M}_{\ell..r}^{(k)}.$

∎

## Acknowledgements

We want to thank Xin Lyu, Edward Pyne, Salil Vadhan and Hongxun Wu for helpful
discussions.

## References

  * [AB09] Sanjeev Arora and Boaz Barak  “Computational complexity: a modern approach”  Cambridge University Press, 2009
  * [AKMPSV20] AmirMahdi Ahmadinejad et al.  “High-precision estimation of random walks in small space”  In _FOCS 2020_ , 2020
  * [AKS87] Miklós Ajtai, János Komlós and Endre Szemerédi  “Deterministic Simulation in LOGSPACE”  In _Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA_ ACM, 1987, pp. 132–140  URL: https://doi.org/10.1145/28395.28410
  * [APPSV23] AmirMahdi Ahmadinejad et al.  “Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification”  In _FOCS 2023, to appear_ , 2023
  * [BCG20] Mark Braverman, Gil Cohen and Sumegha Garg  “Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs”  In _SIAM Journal on Computing_ 49.5, 2020, pp. STOC18-242-STOC18–299  URL: https://doi.org/10.1137/18M1197734
  * [BHPP22] Andrej Bogdanov, William M Hoza, Gautam Prakriya and Edward Pyne  “Hitting sets for regular branching programs”  In _37th Computational Complexity Conference (CCC 2022)_ , 2022  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [BRRY14] Mark Braverman, Anup Rao, Ran Raz and Amir Yehudayoff  “Pseudorandom generators for regular branching programs”  In _SIAM Journal on Computing_ 43.3 SIAM, 2014, pp. 973–986
  * [CDRST21] Gil Cohen et al.  “Error Reduction for Weighted PRGs Against Read Once Branching Programs”  In _36th Computational Complexity Conference (CCC 2021)_ Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 22:1–22:17  URL: https://doi.org/10.4230/LIPIcs.CCC.2021.22
  * [CH20] Kuan Cheng and William M Hoza  “Hitting sets give two-sided derandomization of small space”  In _35th Computational Complexity Conference (CCC 2020)_ , 2020  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [CHLTW23] Lijie Chen et al.  “Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting”  In _FOCS 2023, to appear_ , 2023
  * [CL20] Eshan Chattopadhyay and Jyun-Jie Liao  “Optimal Error Pseudodistributions for Read-Once Branching Programs”  In _35th Computational Complexity Conference, CCC 2020_ 169, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 25:1–25:27
  * [Hoz21] William M Hoza  “Better pseudodistributions and derandomization for space-bounded computation”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)_ , 2021  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [INW94] Russell Impagliazzo, Noam Nisan and Avi Wigderson  “Pseudorandomness for network algorithms”  In _Proceedings of the twenty-sixth annual ACM symposium on Theory of computing_ , 1994, pp. 356–364
  * [LPV23] Chin Ho Lee, Edward Pyne and Salil Vadhan  “On the Power of Regular and Permutation Branching Programs”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), to appear_ , 2023
  * [MRSV17] Jack Murtagh, Omer Reingold, Aaron Sidford and Salil Vadhan  “Derandomization beyond connectivity: Undirected laplacian systems in nearly logarithmic space”  In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2017, pp. 801–812  IEEE
  * [MRT19] Raghu Meka, Omer Reingold and Avishay Tal  “Pseudorandom generators for width-3 branching programs”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019_ ACM, 2019  URL: https://doi.org/10.1145/3313276.3316319
  * [Nis92] Noam Nisan  “Pseudorandom generators for space-bounded computation”  In _Comb._ 12.4, 1992, pp. 449–461  URL: https://doi.org/10.1007/BF01305237
  * [Nis94] Noam Nisan  “RL $\subseteq$ SC”  In _Comput. Complex._ 4, 1994, pp. 1–11  URL: https://doi.org/10.1007/BF01205052
  * [PV21] Edward Pyne and Salil Vadhan  “Pseudodistributions that beat all pseudorandom generators”  In _36th Computational Complexity Conference (CCC 2021)_ , 2021  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [RTV06] Omer Reingold, Luca Trevisan and Salil Vadhan  “Pseudorandom walks on regular digraphs and the RL vs. L problem”  In _Proceedings of the thirty-eighth annual ACM symposium on Theory of computing_ , 2006, pp. 457–466
  * [RV05] Eyal Rozenman and Salil Vadhan  “Derandomized squaring of graphs”  In _International Workshop on Approximation Algorithms for Combinatorial Optimization_ , 2005, pp. 436–447  Springer
  * [SZ99] Michael E. Saks and Shiyu Zhou  “BPHSpace(S) $\subseteq$ DSPACE(S${}^{\mbox{3/2}}$)”  In _J. Comput. Syst. Sci._ 58.2, 1999, pp. 376–403  URL: https://doi.org/10.1006/jcss.1998.1616

##  Appendix A Proof of Lemma 2.2

###### Proof.

$\displaystyle\sum_{i+j\in\\{k-1,k\\}}\varepsilon^{(i)}\varepsilon^{(j)}$
$\displaystyle=\frac{(k+1)^{2}\varepsilon^{(k)}}{10\log(n)}\cdot\left(\gamma\sum_{i+j=k}\frac{1}{(i+1)^{2}(j+1)^{2}}+\sum_{i+j=k-1}\frac{1}{(i+1)^{2}(j+1)^{2}}\right)$
$\displaystyle=\frac{(k+1)^{2}\varepsilon^{(k)}}{10\log(n)}\cdot\left(\gamma\sum_{i+j=k}\frac{\frac{1}{(i+1)^{2}}+\frac{1}{(j+1)^{2}}}{(i+1)^{2}+(j+1)^{2}}+\sum_{i+j=k-1}\frac{\frac{1}{(i+1)^{2}}+\frac{1}{(j+1)^{2}}}{(i+1)^{2}+(j+1)^{2}}\right)$
$\displaystyle\leq\frac{(k+1)^{2}\varepsilon^{(k)}}{10\log(n)}\cdot\left(\gamma\sum_{i+j=k}\frac{\frac{1}{(i+1)^{2}}+\frac{1}{(j+1)^{2}}}{(k+2)^{2}/2}+\sum_{i+j=k-1}\frac{\frac{1}{(i+1)^{2}}+\frac{1}{(j+1)^{2}}}{(k+1)^{2}/2}\right)$
$\displaystyle\leq\frac{\varepsilon^{(k)}}{10\log(n)}\cdot\left(4(1+\gamma)\sum_{i=0}^{k}\frac{1}{(i+1)^{2}}\right)$
$\displaystyle\leq\frac{\varepsilon^{(k)}}{\log(n)}.$

∎

##  Appendix B Proof of Lemma 3.9

###### Proof.

For $\mathsf{sq}_{\ell}=(i_{0},\ldots,i_{h_{\ell}})\in\mathsf{IS}_{\ell..m}$
and $\mathsf{sq}_{r}=(j_{0},\ldots,j_{h_{r}})\in\mathsf{IS}_{m..r}$, define

$\mathsf{sq}_{\ell}\|\mathsf{sq}_{r}=(i_{0},\ldots,i_{h_{\ell}}=j_{0},\ldots,j_{h_{r}}).$

Observe that $\mathsf{sq}_{\ell}||\mathsf{sq}_{r}$ has length
$h_{\ell}+h_{r}$, and that
$\mathbf{M}_{\mathsf{sq}_{\ell}||\mathsf{sq}_{r}}^{(0)}=\mathbf{M}_{\mathsf{sq}_{\ell}}^{(0)}\cdot\mathbf{M}_{\mathsf{sq}_{r}}^{(0)}$.

With the notation above, we prove the lemma by induction over
$t:=\log(r-\ell)$ and $k$. The base cases $t=0$ or $k=0$ are trivial. Consider
the recursive formula (1), and let $S_{\ell}^{(i)},S_{r}^{(j)}$ denote the
corresponding sets of $\mathbf{M}_{\ell..m}^{(i)}$ and
$\mathbf{M}_{m..r}^{(j)}$ respectively. By distributive law, we get

$\mathbf{M}_{\ell..r}^{(k)}=\sum_{b\in\\{0,1\\}}\sum_{i+j=k-b}\sum_{(\mathsf{sq_{\ell}},\sigma)\in
S_{\ell}^{(i)}}\sum_{(\mathsf{sq_{r}},\sigma)\in
S_{r}^{(j)}}(-1)^{b}\sigma_{\ell}\sigma_{r}\mathbf{M}_{\mathsf{sq}_{\ell}\|\mathsf{sq}_{r}}^{(0)}.$

Therefore, we can define

$S=\bigcup_{b\in\\{0,1\\}^{0,1},i+j=k-b}\\{(\mathsf{sq}_{\ell}\|\mathsf{sq}_{r},(-1)^{b}\sigma_{\ell}\sigma_{r}):(\mathsf{sq_{\ell}},\sigma)\in
S_{\ell}^{(i)}\wedge(\mathsf{sq_{r}},\sigma)\in S_{r}^{(j)}\\},$

which satisfies the first condition. Based on the induction hypothesis, the
length of each $\mathsf{sq}_{\ell}\|\mathsf{sq}_{r}$ is at most
$(i+j)(t-1)+2\leq k(t-1)+2\leq kt+1$, and the size of $S$ is at most

$\sum_{i+j\in\\{k-1,k\\}}\left|S_{\ell}^{(i)}\right|\left|S_{r}^{(j)}\right|\leq(2k+1)2^{2k(t-1)}\leq
2^{2kt}.$

∎

##  Appendix C Base-case space complexity

In this section we prove the following claim.

######  Lemma C.1.

There is an algorithm which for every $\ell<r$ can compute
$\mathbf{M}_{\ell..r}^{(0)}$ in space $\tilde{O}(\log(nw))$.

###### Proof.

We claim that it is possible to output the indices
$(\ell_{0},r_{0})\in\mathsf{BS}_{n}$ of all the factors
$\mathbf{M}_{\ell_{0}..r_{0}}^{(0)}$ in the expansion of
$\mathbf{M}_{\ell..r}^{(0)}$ in space $O(\log(n))$, and there are only
$2\log(n)$ factors. The claim then follows by Lemma 4.2, Lemma 2.4 and Lemma
2.5.

For the base cases $(\ell,r)\in\mathsf{BS}_{n}$ the claim is straightforward.
For $(\ell,r)\not\in\mathsf{BS}_{n}$, first compute $m=\mathsf{LCA}(\ell,r)$,
and note that
$\mathbf{M}_{\ell..r}^{(0)}=\mathbf{M}_{\ell..m}^{(0)}\mathbf{M}_{m..r}^{(0)}$.
For the factors of $\mathbf{M}_{\ell..m}^{(0)}$, while
$(\ell,m)\not\in\mathsf{BS}_{n}$, we repeatedly compute
$m^{\prime}=\mathsf{LCA}(\ell,m)$, then output $(m^{\prime},m)$, and replace
$m$ with the value of $m^{\prime}$. Eventually when
$(\ell,m)\in\mathsf{BS}_{n}$ we output $(\ell,m)$.

Note that
$\mathbf{M}_{\ell..m}^{(0)}=\mathbf{M}_{\ell..m^{\prime}}^{(0)}\mathbf{M}_{m^{\prime}..m}^{(0)}$,
so if we can prove that $(m^{\prime},m)\in\mathsf{BS}_{n}$, then what we
output is exactly the indices of the expansion (except that the output order
is reversed, which is easy to deal with). To prove that
$(m^{\prime},m)\in\mathsf{BS}_{n}$, assume that $m^{\prime}=c^{\prime}\cdot
2^{t^{\prime}}$ and $m=c\cdot 2^{t}$, for some odd integers $c^{\prime},c$. In
our algorithm, we always have $m^{\prime}=\mathsf{LCA}(\ell,m)$ and
$m=\mathsf{LCA}(\ell,r^{\prime})$ for some $r^{\prime}>m$. Because
$\ell<m^{\prime}<m<r^{\prime}$, by definition of $\mathsf{LCA}$ we must have
$t>t^{\prime}$. We claim that we must have $m=m^{\prime}+2^{t^{\prime}}$,
which implies $(m^{\prime},m)\in\mathsf{BS}_{n}$.

If this is not the case, then we must have
$m^{\prime}<m^{\prime}+2^{t^{\prime}}<m$ because $m$ is also a multiple of
$m$. Then observe that $m^{\prime}+2^{t^{\prime}}$ is a multiple of
$2^{t^{\prime}+1}$, which contradicts to the fact that
$m^{\prime}=\mathsf{LCA}(\ell,m)$.

Now we have proved how to output the expansion indices of
$\mathbf{M}_{\ell.m}^{(0)}$, and for $\mathbf{M}_{m..r}^{(0)}$ the proof is
basically the same. Finally, to prove that there are at most $2\log(n)$
factors, observe that every time we replace $m$ with $m^{\prime}$, the
exponent $t$ strictly decreases. Because we always have $0\leq t<\log(n)$, the
procedure above can repeat at most $\log(n)$ iterations. Therefore both
$\mathbf{M}_{\ell.m}^{(0)}$ and $\mathbf{M}_{m..r}^{(0)}$ have at most
$\log(n)$ factors.

∎

##  Appendix D Equivalence between the constructions in [CHLTW23] and [CL20]

The construction in [CHLTW23] is based on the inverse Laplacian perspective of
derandomization [AKMPSV20] and preconditioned Richardson iteration, which we
briefly recap as follows. Consider the block matrix
$\mathbf{W}=(\mathbf{R}^{w\times w})^{(n+1)\times(n+1)}$ s.t.
$\mathbf{W}[i-1,i]=\mathbf{M}_{i}$ for every $i\in[n]$, and other entries of
$\mathbf{W}$ are $0$. The Laplacian is defined as
$\mathbf{L}:=\mathbf{I}-\mathbf{W}$, which is an invertible matrix. It can be
shown that each entry $\mathbf{L}^{-1}[i,j]$ in the inverse Laplacian
$\mathbf{L}^{-1}$ is exactly $\mathbf{M}_{i..j}$ (where
$\mathbf{M}_{i..i}=\mathbf{I}_{w}$ and $\mathbf{M}_{i..j}=0$ if $i>j$).

To approximate $\mathbf{M}_{0..n}$ within error $\varepsilon$, [CHLTW23]
followed the preconditioned Richardson iteration approach, which first
constructs a “mild approximation” of $\mathbf{L}^{-1}$ denoted by
$\widetilde{\mathbf{L}^{-1}}$. Their construction of
$\widetilde{\mathbf{L}^{-1}}$ is based on the shortcut graph structure, and
one can verify that their $\widetilde{\mathbf{L}^{-1}}[i,j]$ is actually the
same as $\mathbf{M}_{i..j}^{(0)}$ defined in this paper.

Given $\mathbf{L}^{-1}$, the construction based on Richardson iteration is
defined as
$(\mathbf{L}^{-1})^{(k)}=\widetilde{\mathbf{L}^{-1}}\sum_{i=0}^{k}(\mathbf{I}-\mathbf{L}\widetilde{\mathbf{L}^{-1}})^{i}$,
and $(\mathbf{L}^{-1})^{(k)}[0,n]$ is the final output. Observe that this
formula satisfies the recursion
$(\mathbf{L}^{-1})^{(k)}=\widetilde{\mathbf{L}^{-1}}+(\mathbf{L}^{-1})^{(k-1)}(\mathbf{I}-\mathbf{L}\widetilde{\mathbf{L}^{-1}})$.
In addition, observe that for every $i<j$,
$(\mathbf{I}-\mathbf{L}\widetilde{\mathbf{L}^{-1}})[i,j]=\mathbf{M}_{i+1}\mathbf{M}_{i+1..j}^{(0)}-\mathbf{M}_{i..j}^{(0)}$,111111This
is in fact the _local consistency error_ defined in [CH20], as observed in
[Hoz21]. and other entries of
$\mathbf{I}-\mathbf{L}\widetilde{\mathbf{L}^{-1}}$ are $0$. Therefore, for
every $\ell\leq r$ we have

$(\mathbf{L}^{-1})^{(k)}[\ell,r]=\mathbf{M}_{\ell..r}^{(0)}+\sum_{s=\ell+1}^{r}(\mathbf{L}^{-1})^{(k-1)}[\ell,s-1]\left(\mathbf{M}_{s}\mathbf{M}_{s..r}^{(0)}-\mathbf{M}_{s-1..r}^{(0)}\right).$

Comparing it with the special case $h=k$ of Lemma 4.7:

$\mathbf{M}_{\ell..r}^{(k)}=\sum_{s=\ell+1}^{r}\mathbf{M}_{\ell..s-1}^{(k-1)}\mathbf{M}_{s}\mathbf{M}_{s..r}^{(0)}-\sum_{s=\ell+1}^{r-1}\mathbf{M}_{\ell..s}^{(k-1)}\mathbf{M}_{s..r}^{(0)}.$

Using the fact that $(\mathbf{L}^{-1})^{(k-1)}[\ell,\ell]=\mathbf{I}$, it is
relatively easy to prove via induction that
$(\mathbf{L}^{-1})^{(k)}[\ell,r]=\mathbf{M}_{\ell,r}^{(k)}$.