Proof. Let \(\mathsf{R}=\mathsf{R}^{(1)}\circ\mathsf{R}^{(2)}\) and \(\sigma=\sigma^{(1)}\cdot \sigma^{(2)}\). For any \(f\in \mathcal{F}_0\), we have: \[\begin{align} &\left|\mathbb{E}_U f(U)-\frac{1}{2^{d_1+d_2}}\sum_{i_1\in \{0,1\} ^{d_1},i_2\in \{0,1\} ^{d_2}} \sigma(i_1,i_2)\mathbb{E}_{U_{s_2}} \left[f(\mathsf{R}_{(i_1,i_2)}(U_{s_2}))\right]\right|\\ &\leq \left|\mathbb{E}_U f(U)-\frac{1}{2^{d_1}}\sum_{i_1\in \{0,1\} ^{d_1}} \sigma^{(1)}(i_1)\mathbb{E}_{U_{s_1}} \left[f(\mathsf{R}^{(1)}_{i_1}(U_{s_1}))\right]\right|\\ &+\frac{1}{2^{d_1}}\sum_{i_1\in \{0,1\} ^{d_1}} |\sigma^{(1)}(i_1)| \left|\mathbb{E}_{U_{s_1}} \left[f(\mathsf{R}^{(1)}_{i_1}(U_{s_1}))\right]-\frac{1}{2^{d_2}}\sum_{i_2\in \{0,1\} ^{d_2}} \sigma^{(2)}(i_2)\mathbb{E}_{U_{s_2}} \left[f(\mathsf{R}^{(2)}_{i_2}(U_{s_2}))\right]\right|\\ &\leq \varepsilon_1+K_1\varepsilon_2. \end{align}\]

Furthermore, \(|\sigma(i_1,i_2)|\leq |\sigma^{(1)}(i_1)|\cdot |\sigma^{(2)}(i_2)|\leq K_1K_2\). For any \(i_1,i_2\), \(x\mapsto f(\mathsf{R}^{(1)}_{i_1}(x))\in \mathcal{F}_{1}\), sp we can apply \(\mathsf{R}^{(2)}_{i_2}\) to this mapping, therefore \(x\mapsto f(\mathsf{R}_{(i_1,i_2)}(x))\in \mathcal{F}_{2}\). The seed length is \(d_1+d_2\). The function is explicit since both components are explicit. ◻

Proof. We prove this by induction on \(k\). The base case \(k=2\) is shown by 1. Suppose the statement holds for \(k-1\), then \((\mathsf{R}^{(1)}\circ\ldots\circ\mathsf{R}^{(k-1)},\sigma^{(1)}\cdot \ldots\cdot \sigma^{(k-1)})\) is an explicit \((\sum_{i=1}^{k-1} d_i,\prod_{i=1}^{k-1} K_i,\sum_{i=1}^{k-1} \left(\prod_{j=1}^{i-1}K_j\right)\varepsilon_i)\)-weighted pseudorandom reduction from \(\mathcal{F}_0\) to \(\mathcal{F}_{k-1}\). Then we can apply Lemma 1 on \((\mathsf{R}^{(1)}\circ\ldots\circ\mathsf{R}^{(k-1)},\sigma^{(1)}\cdot \ldots\cdot \sigma^{(k-1)})\) and \((\mathsf{R}^{(k)},\sigma^{(k)})\), which gives the desired result. ◻

Proof. Let \(\mathrm{E\mathrm{\small xt}}:\{0, 1\}^{3s} \times \{0,1\}^d \rightarrow \{0, 1\}^{s}\) be a \((2s,\frac{\varepsilon}{3n})\)-extractor with seed length \(d=C_{GUV}\cdot \log \frac{ns}{\varepsilon}\) from Theorem 6. Let \(\mathsf{NZ}\) be defined as in 4. We define the reduction \((\mathsf{R},\sigma)\): \[\begin{align} &\mathsf{R}_x(y):=\mathsf{NZ}(x,y)\\ &\sigma_x:= 1. \end{align}\] Now consider that we fix \(x\) and let \(y_i\)’s be free. We need to prove that the reduction \((\mathsf{R},\sigma)\) is a \((3s,1,\varepsilon)\)-weighted pseudorandom reduction.

Let \(f\in \mathcal{B}_{(n,s,w)}\), then by 4, \[|\mathbb{E}f-2^{-3s}\sum_{x\in \{0,1\}^{3s}}\mathbb{E}f(\mathsf{NZ}(x,*))|=|\mathbb{E}f-\mathbb{E}f(\mathsf{NZ}(X,Y))|\leq \varepsilon.\] Therefore, \((\mathsf{R},\sigma)\) approximates \(f\) with error at most \(\varepsilon\).

To prove that \(f(\mathsf{NZ}(x,*))\in \mathcal{B}_{(n,d,w)}\) for all \(f\in \mathcal{B}_{(n,s,w)}\) and \(x\in \{0,1\}^{3s}\), \(y\in \{0,1\}^{d}\). We construct the ROBP \(g_x:=f(\mathsf{NZ}(x,*))\) as follows:

Let \(V_0,\ldots,V_n\) be the layers of \(f\), each consisting of \(w\) nodes. The ROBP \(g_x\) is also defined on \(V_0,\ldots,V_n\). The labeled edge set of \(g_x\) is defined as follows: \[\begin{align} E_{g_x}=\{(u,v,y):u\in V_{i-1},v\in V_i, y\in \{0,1\}^{d}, \exists \text{ an edge from u to v labeled by \mathrm{E\mathrm{\small xt}}(x,y) in f}\} \end{align}\] The start node and accept nodes of \(G\) are the same as those in \(f\). Then \(g_x\) is in \(\mathcal{B}_{(n,d,w)}\) and \(g_x(y_1,\ldots,y_n)=f(\mathrm{E\mathrm{\small xt}}(x,y_1),\ldots,\mathrm{E\mathrm{\small xt}}(x,y_n))=f(\mathsf{NZ}(x,y))\). ◻

Proof of Lemma 6. Let \(k,K,n_{i,j},\sigma'_i\) be as in Theorem 7, Let \(\mathsf{PRG}\) be a \(\varepsilon/(2(n+1))\)-PRG for \(\mathcal{B}_{(n,s,w)}\) with seed length \(d\) in the assumption. We define the reduction \((\mathsf{R},\sigma)\) as follows: \[\begin{align} &\mathsf{R}_i(x_1,\ldots,x_k)=\mathsf{PRG}(x_1)_{n_{i,1}}, \mathsf{PRG}(x_2)_{n_{i,2}-n_{i,1}}, \ldots, \mathsf{PRG}(x_k)_{n_{i,k}-n_{i,k-1}}\\ &\sigma_i=\sigma'_i K. \end{align}\] Here \(\mathsf{PRG}(x_i)_{c}\) denotes the first \(c\) symbols of \(\mathsf{PRG}(x_i)\) and each symbol is in \(\{0,1\}^s\).

We will show that \((\mathsf{R},\sigma)\) is a \(( \log K, K,\varepsilon^{\frac{k+1}{2}}\cdot(n+1))\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n,s,w)}\) to \(\mathcal{B}_{(k,d,w)}\).

Let \(f\in \mathcal{B}_{(n,s,w)}\). Recall that \(f^{[i,j]}(x)\) denotes the transition matrix of \(f\) from layer \(i\) to layer \(j\) with input \(x=(x_1,\ldots,x_{j-i})\). Define \(A_i=\mathbb{E}_{x\in \{0,1\}^s}f^{[i-1,i]}[x]\) and \(B_{i,j}=\mathbb{E}_{x\in \{0,1\}^d}f^{[i,j]}[\mathsf{PRG}(x)_{j-i}]\). By the definition of the PRG, we have \(\|B_{i,j}-A_{i+1}\ldots A_j\|_\infty\leq \varepsilon/(n+1)\).

Therefore, by 7, \[\begin{align} &\left| \mathbb{E}f-\frac{1}{K}\sum_{i=1}^K \sigma(i)\mathbb{E}_{X} f(\mathsf{R}_i(X))\right|\\ =& \left\lVert \mathbb{E}f^{[0,n]} - \sum_{i=1}^K \sigma_i \mathbb{E}f^{[0,n]}(\mathsf{PRG}(X_1)_{n_{i,1}}, \mathsf{PRG}(X_2)_{n_{i,2}-n_{i,1}},\ldots,\mathsf{PRG}(X_k)_{n_{i,k}-n_{i,k-1}})\right\rVert_\infty\\ \leq& \left\lVert \mathbb{E}f^{[0,n]}- \sum_{i=1}^K \sigma_i \mathbb{E}f^{[0,n_{i,1}]}(\mathsf{PRG}(X_1)_{n_{i,1}})\mathbb{E}f^{[n_{i,1},n_{i,2}]}(\mathsf{PRG}(X_2)_{n_{i,2}-n_{i,1}})\cdots \right.\\ &\qquad\qquad\qquad\left. \vphantom{\sum_{i=1}^K} \cdots\mathbb{E}f^{[n_{i,k-1},n_{i,k}]}(\mathsf{PRG}(X_k)_{n_{i,k}-n_{i,k-1}})\right\rVert_\infty\\ =& \left\lVert A_1\ldots A_n - \sum_{i=1}^K \sigma_i B_{0,n_{i,1}}B_{n_{i,1},n_{i,2}}\ldots B_{n_{i,k-1},n_{i,k}}\right\rVert_\infty\\ \leq& \varepsilon^{\frac{k+1}{2}}\cdot(n+1). \end{align}\]

The weight is \(K=(8n)^{k+1}\) by 7, and so the seed length is \(\log K=O(k\log n)\).

Finally, we need to show that \(f\circ \mathsf{R}_i \in \mathcal{B}_{(k,d,w)}\) for all \(f\in \mathcal{B}_{(n,s,w)}\) and \(i \in [K]\). We construct the ROBP \(g:=f\circ \mathsf{R}_i\) as follows:

Let \(V_0,\ldots,V_n\) be the layers of \(f\), each consisting of \(w\) nodes. The ROBP \(g\) is defined on \(V_0,V_{n_{i,1}},\ldots,V_{n_{i,k}}\). The labelled edge set of \(g\) is defined as follows: \[\begin{align} E_g= \{ & (u,v,x): j\in [n], u\in V_{n_{i,j-1}}, v\in V_{n_{i,j}}, x\in \{0,1\}^{d}, \\ & \text{there exists a path from u to v in f through \mathsf{PRG}(x)_{n_{i,j}-n_{i,j-1}} } \} \end{align}\] The start node and accept nodes of \(g\) are the same as that in \(f\). Then \(g\) is in \(\mathcal{B}_{(k,d,w)}\) and \(g(x_1,\ldots,x_n)=f(\mathsf{PRG}(x_1)_{n_{i,1}}, \mathsf{PRG}(x_2)_{n_{i,2}-n_{i,1}}, \ldots,\mathsf{PRG}(x_k)_{n_{i,k}-n_{i,k-1}})=f(\mathsf{R}_i(x_1,\ldots,x_k))\). ◻

Proof. Fix \(c,C\) to be constants. We use Armoni’s PRG⁷ for \(\mathcal{B}_{(n,C\log w,w)}\) with error \(\varepsilon_0=\frac{2^{-\frac{a\log w}{n^{1/c}}}}{(n+1)^2}\). By 8, the seed length is \(O\left(C\log w+\frac{a\log w\log \log w}{\log\log w/c+O(1)}\right)=C' \log w\), where \(C'\) depends on \(c, C, a\). Then we can set \(k=2 n^{1/c} \ge \frac{a\log w+\log n}{1/2\cdot\log(1/\varepsilon_0)}\) in Lemma 6 and invoke it to attain this lemma. ◻

Proof. We use Armoni’s PRG for \(\mathcal{B}_{(n,s,w)}\) with error \(\varepsilon_0=\frac{2^{-2a\sqrt{\log n\log w}}}{(n+1)}\). By 8, the seed length is \(O\left(s+\frac{\log n\log (nw)}{\log\log w-\log\log n}\right)\). Then we can set \(k=\frac{a\log w+\log n}{1/2\cdot \log(1/\varepsilon_0)}\leq \sqrt{\frac{\log w}{\log n}}\leq \log^{1/2} w\) in Lemma 6 and invoke it to attain this lemma. ◻

Proof. We set up the reductions as the following, which is also illustrated in 1.

We have the following reductions:

Let \((\mathsf{R}^{(1)},\sigma^{(1)})\) be a \((d_1,K_1, \varepsilon/4)\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n,s,w)}\) to \(\mathcal{B}_{(n_1,s_1,w)}\) given by Lemma [lem:armoni32reduction], where

• \(d_1=O(\log w)\),

• \(n_1=\min\{n,\log^{1/2} w\}\),

• \(s_1=O(s+\frac{\log n\log (nw)}{\log\log w-\log\log n})\),

• \(K_1=(8n)^{\sqrt{\frac{\log w}{\log n}}+1}\).

Let \((\mathsf{R}^{(2)},\sigma^{(2)})\) be a \((s_2,K_2, \varepsilon/(4K_1))\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n_1,s_1,w)}\) to \(\mathcal{B}_{(n_2,s_2,w)}\) given by Lemma 5, where

• \(d_2=O(s+\frac{\log n\log (nw)}{\log\log w-\log\log n})\),

• \(n_2=n_1\),

• \(s_2\leq 2C_{GUV}\log (1/\varepsilon)\),

• \(K_2=1\).

Using 1, \((\mathsf{R}^{(1)}\circ \mathsf{R}^{(2)},\sigma^{(1)}\cdot \sigma^{(2)})\) is a \((d_1+d_2,K_1,\varepsilon/2)\) weighted pseudorandom reduction from \(\mathcal{B}_{(n,s,w)}\) to \(\mathcal{B}_{(\log^{1/2} w, 2C_{GUV}\log (1/\varepsilon),w)}\). We set \(\varepsilon'=(\varepsilon/K_1)^2\) and continue the reduction with the following parameters:

\(n_3=\log^{1/2} w,n_{i+1}=n_i^{1/3}\) for \(i=3,\ldots,l-1\). \(n_l=\frac{\log w}{\log 1/\varepsilon'}+2=\frac{\log w}{\log 1/\varepsilon+\sqrt{\log n\log w}}+2\).

It is clear that \[l=\log\log\min\{n,\log w\}-\log\log\left(\frac{\log w}{\log n/\varepsilon}+2\right)+O(1).\]

For \(i=3,\ldots,l-1\), let \((\mathsf{R}^{(i)},\sigma^{(i)})\) be a \((d_i,K_i, \varepsilon')\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n_i,2C_{GUV}\log (1/\varepsilon'),w)}\) to \(\mathcal{B}_{(n_{i+1},C_{large}\log w,w)}\) given by Lemma 7, setting constants \(c =3\), \(C = \frac{2C_{GUV}\log (1/\varepsilon')}{\log w}\), \(a= \log_w (1/\varepsilon')\) in 7, where

• \(d_i= \log K_i = O(n_i^{1/2}\log n_i)\),

• \(K_i=\exp(O(n_i^{1/2}\log n_i))\).

Notice that since \(n_3=\log^{1/2} w\) and \(n_i\) is monotonously decreasing, the condition \(n_i\leq \log^3 w\) is always satisfied, so the condition in 7 is always met.

For \(i=3,\ldots,l-2\), let \((\widehat{\mathsf{R}}^{(i)},\widehat{\sigma}^{(i)})\) be a \((\widehat{d}_i,\widehat{K}_i, \varepsilon')\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n_{i+1},C_{large}\log w,w)}\) to \(\mathcal{B}_{(n_{i+1}, 2C_{GUV}\log (1/\varepsilon'),w)}\) given by Lemma 5, where

• \(\widehat{d}_i=O(\log w)\),

• \(\widehat{K}_i=1\).

We invoke 2 to compose the \(2l-7\) reductions, which gives \((\mathsf{R}^{(3)}\circ \widehat{\mathsf{R}}^{(3)}\circ \mathsf{R}^{(4)}\circ \widehat{\mathsf{R}}^{(4)}\circ \ldots \circ \mathsf{R}^{(l-1)},\sigma^{(3)}\cdot \widehat{\sigma}^{(3)}\cdot \sigma^{(4)}\cdot \widehat{\sigma}^{(4)}\cdot \cdots \cdot \sigma^{(l-1)})\). Also by 2, we know the reduction is a \((d^*,K^*,\varepsilon^*)\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n,s,w)}\) to \(\mathcal{B}_{(n_l, 2C_{GUV}\log (1/\varepsilon'),w)}\). The latter class is contained in \(\mathcal{B}_{(O(1),C_{GUV}\log w,w)}\).The parameters \((d^*,K^*,\varepsilon^*)\) is shown as following:

• \(d^*=\sum_{i=3}^{l-1}d_i=O(l\log w)\),

• \(K^*=\prod_{i=3}^{l-1}K_i\cdot \widehat{K}_i=\exp(\sum_{i=3}^{l-1}n_i^{1/2}\log n_i)\leq \exp(l\log^{1/3} w)<\exp(\log^{1/2} w)\),

• \(\varepsilon^*=\sum_{i=3}^{l-1}\varepsilon'\cdot \prod_{j=3}^{i-1}K_j\cdot \widehat{K}_j\leq l\cdot \varepsilon\cdot K<\varepsilon'\cdot \exp(\log^{1/2} w)<\varepsilon/(2K_1)\).

We invoke 1 again and compose the \((d_1+d_2,K_1,\varepsilon/2)\)-weighted pseudorandom reduction from \(\mathcal{B}_{(n,s,w)}\) to \(\mathcal{B}_{(\log^{1/3} w,2C_{GUV}\log (1/\varepsilon),w)}\) with the \((d^*,K^*,\varepsilon^*)\)-weighted pseudorandom reduction from \(\mathcal{B}_{(\log^{1/3} w,2C_{GUV}\log (1/\varepsilon),w)}\) to \(\mathcal{B}_{(O(1),C_{GUV}\log w,w)}\). We get the desired reduction with the following parameters:

• Seed length: \(s_1+s_2+s^*=O(s+\frac{\log n\log (nw)}{\log\log w-\log\log n}+\log w (\log\log\log w-\log\log\frac{\log w}{\log (n/\varepsilon)})\),

• Weight: \(K_1\cdot K^*\leq (8n)^{2\sqrt{\frac{\log w}{\log n}}}\),

• Error: \(\varepsilon/2+K_1\cdot \varepsilon/(2K_1)=\varepsilon\).

The lemma follows. ◻

Proof. Let \((\mathsf{R},\sigma)\) be the reduction from Lemma 9. We construct the WPRG \((G,w)\) with the same weight function \(w\) and \(G\) is defined as \(G(x,i)=\mathsf{R}(x,i)\). By 9, to fool the original ROBP we only need to provide randomness for the seed of \((\mathsf{R},\sigma)\) and also provide a random string \(x\) which can fool an arbitrary ROBP in \(\mathcal{B}_{(O(1),C_{GUV}\log w,w)}\). We use true randomness for \(x\) and this only takes \(O(\log w)\) random bits. Also the randomness used by \((\mathsf{R},\sigma)\) is \(O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}+\log w (\log\log\log w-\log\log\frac{\log w}{\log (n/\varepsilon)})\right)\). So the total seed length is as stated. The weight also directly follows from 9. ◻

Proof. Let \((G_0,\sigma_0)\) be a \(1/(2w\cdot (n+1)^2)\)-WPRG for \(\mathcal{B}_{(n,s,w)}\) with seed length \[d=O\left(s+\frac{\log n\log (nw)}{\log\log w-\log\log n}+\log w (\log\log\min\{n,\log w\}-\log\log\frac{\log w}{\log (n/\varepsilon)})\right)\] and weight \(K=\mathop{\mathrm{\mathrm{poly}}}(nw/\varepsilon)\) given by Lemma 3.

Let \(\mathrm{Samp}\) be a \((1/(2W\cdot w^2\cdot (n+1)^2),\varepsilon/(2(2n)^k\cdot \sigma^{k}))\)-averaging sampler with seed length \(r=d+O(\log(nw/\varepsilon))\) and \(p=O(\log(nw)+\log\log(1/\varepsilon))\) given by Lemma 11.

By Lemma 12, we get a \(\varepsilon\)-WPRG for \(\mathcal{B}_{(n,s,w)}\) with seed length \[\begin{align} &r+(2k+1)p+(2k+1)s\\ = &O\left(s\cdot\frac{\log(n/\varepsilon)}{\log(nw)}+\frac{\log n\log (nw)}{\log\log w-\log\log n}+\log w (\log\log\min\{n,\log w\}-\log\log\frac{\log w}{\log (n/\varepsilon)})+\log(1/\varepsilon)\right) \end{align}\] and weight \(\mathop{\mathrm{\mathrm{poly}}}(nw/\varepsilon)\). ◻

Proof of 10. In the case of \(w>n\), 20 already gives a suitable WPRG. So we assume \(w\leq n\). Denote \(f\in\mathcal{B}_{n,s,w}\) as the original regular ROBP. Let \((\mathsf{R},\sigma)=\{(\mathsf{R}_i,\sigma_i)\}_{i\in [K]}\) be the \((\log K, K, \varepsilon/2)\) -reduction from \(\mathcal{R}_{n,s,w}\) to \(\mathcal{B}_{n_1,s_1,w}\), given by 11, where \(K=n^{O(\sqrt{\log(1/\varepsilon})}, n_1=O(\log n\sqrt{\log(1/\varepsilon)})\), and \[s_1=O\left(s+\log n\left(\sqrt{\log(1/\varepsilon)}+\log w + \log(\mathsf{W}(f))+\log\log n\right)\right).\] Then we have \[\begin{align} &\left|\mathbb{E}[f]-\sum_{i\in[K]}\frac{\sigma_i}{K}\cdot \mathbb{E}_{x\in (\{0,1\}^{s_1})^{n_1}}\left[f(\mathsf{R}_i(x)\right]\right|\leq \varepsilon/2, \end{align}\] in which \(|\sigma_i|\leq K\). Let \((G,\sigma'):\{0,1\}^d\to (\{0,1\}^{s_1})^{n_1}\times \mathbb{R}\) be the \(\varepsilon/(2K)\)-WPRG given by 20. We have

\[\begin{align} &\left|\mathbb{E}[f]-\sum_{i\in [K]}\frac{\sigma_i}{K}\cdot \sum_{y\in\{0,1\}^d}\frac{\sigma'(y)}{2^d} \left[f(\mathsf{R}_i(G(y))\right]\right|\\ \leq& \left|\mathbb{E}[f]-\sum_{i\in[K]}\frac{\sigma_i}{K}\cdot \mathbb{E}_{x\in (\{0,1\}^{s_1})^{n_1}}\left[f(\mathsf{R}_i(x)\right]\right| +\sum_{i\in[K]}\frac{\sigma_i}{K}\left| \mathbb{E}_{x\in (\{0,1\}^s)^r}\left[f(\mathsf{R}_i(x)\right]-\sum_{y\in\{0,1\}^d}\frac{\sigma'(y)}{2^d} \left[f(\mathsf{R}_i(G(y))\right] \right|\\ \leq& \varepsilon/2+K\cdot \varepsilon/(2K)=\varepsilon. \end{align}\] Therefore \((\mathsf{R}\circ G, \sigma\cdot \sigma')\) is a \(\varepsilon\)-WPRG for \(f\) with seed length \(d_{total}=\log K+d\).

By 20, the \(\varepsilon/(2K)\)-WPRG requires \[\begin{align} d=&O\left(s_1+\frac{\log n_1\log (n_1w)}{\max\left\{1,\log\log w-\log\log n_1\right\}}+\log w \log\log\min\{n_1,\log w\}+\log (K/\varepsilon)\right) \end{align}\] We use the assumption that \(w\leq n\), organize the terms and find \[\begin{align} d_{total}=&O\left(s+\log n\left(\sqrt{\log(1/\varepsilon)}+\log w +\log(\mathsf{W}(f)) +\log\log n\right)+ \log n_1\log n+\log(K/\varepsilon)\right)\\ =& O\left(s+\log n\left(\sqrt{\log(1/\varepsilon)}+\log w +\log(\mathsf{W}(f))+\log\log n\right)+\log(1/\varepsilon)\right), \end{align}\] since \(\log n_1\log (n_1 w) = O( \log n_1 \log n), \log w \log\log\min\{n_1,\log w\} = O(\log n \log n_1)\).

Now we compute the weight, which is the upper bound of \(|\sigma_i|\cdot|\sigma'(x)|\) over \(i\in[K],x\in\{0,1\}^d\). By 20, \(|\sigma'(x)|\leq \mathop{\mathrm{\mathrm{poly}}}(r,w,\varepsilon/2K)=\mathop{\mathrm{\mathrm{poly}}}(n^{{1+\sqrt{\log( 1/\varepsilon)}}},w)\). \(|\sigma_i|\leq K=n^{O(1+\sqrt{\log( 1/\varepsilon)})}\). Therefore, the total weight is bound by \(\mathop{\mathrm{\mathrm{poly}}}(n^{{1+\sqrt{\log( 1/\varepsilon)}}},w)\). ◻

Proof. Let \(G\) be the INW PRG that fools \(\mathcal{P}_{(n,s)}\) with \(\tau\)-sv-error, such that \(\tau=\min\{\frac{\varepsilon^{2/(k+1)}}{16\log^2 n},\frac{1}{64\log^2 n}\}\). Then the seed length is \(d = s+O(\log n(\log\log n+\log 1/\tau))\) by Lemma 14.

We invoke 15 with \(G\) and \(k\), which gives \((G^{(k)},\sigma^{(k)})\). This WPRG fools \(\mathcal{P}_{(n,s)}\) with entrywise error \(\left(4 \cdot \sqrt{\tau} \cdot \log n \right)^{k+1}<\varepsilon\). We define the reduction \((\mathsf{R},\sigma): \mathsf{R}_i(x_1,...,x_r)=G^{(k)}(i,x_1,...,x_r),w_i=\sigma^{(k)}(i)\). By 15, the weight of this reduction is bounded by \(K=n^{O(k)}\). The seed length of the reduction is \(\log K=O(k\log n)\), since we need \(\log K=O(k\log n)\) bits to choose \(i\).

Given any \(f\in \mathcal{P}_{(n,s)}\), notice that each \(f\circ \mathsf{R}_i\) is a permutation ROBP of length \(r=O(k\log n)\) and alphabet size \(2^d=2^{s+O(\log n(\log\log n+\log 1/\tau))}\). The reason is that the transition matrix of \(f\circ \mathsf{R}_i\) from the \(j-1\)-th layer to the \(j\)-th layer on input \(x\in \{0,1\}^{d}\) can be expressed as \((f\circ \mathsf{R}_i)^{[j-1,j]}(x)\). As \((f\circ \mathsf{R})^{[j-1,j]}(x)=f^{[n_{i,j-1},n_{i,j}]}(G(x)_{n_{i,j}-n_{i,j-1}})\) and the latter is a product of \(n_{i,j}-n_{i,j-1}\) permutation matrices, the transition matrix of \(f\circ \mathsf{R}_i\) is also a permutation matrix. Hence \(f\circ \mathsf{R}_i\) is a permutation ROBP. Also, note that each \(f\circ \mathsf{R}_i\) only has one accept node since its accept node is the same as that of \(f\).

Therefore, the reduction is a \((O(k\log n), O(n^k),\varepsilon)\)-weighted pseudorandom reduction. ◻

Proof. Let \((\mathsf{R}^{(0)},\sigma^{(0)})\) be the \((d_0,K_0,\varepsilon/2)\)-weighted pseudorandom reduction from \(\mathcal{P}_{(n,s)}\) to \(\mathcal{P}_{(n_1,s_1)}\) such that \(n_1=O(\log n\sqrt{\log(1/\varepsilon)})\) and \(s_1=s+O(\log n(\log\log n+\sqrt{\log(1/\varepsilon)}))\). This reduction is guaranteed by Lemma 17 and have the following parameters:

1. \(d_0=O(\log n\sqrt{\log(1/\varepsilon)})\),

2. \(K_0=2^{O(\log n\sqrt{\log(1/\varepsilon)})}\).

Now we define a new parameter \(\varepsilon'=\varepsilon/2K_0\). Let \[n_0=n,n_i=\log^3 n_{i-1}\] for each \(i=1,\ldots,l\) and \(n_l= 32768\). It is clear that \(l\leq \log\log n\).

For each \(i=1,\ldots,l\), let \((\mathsf{R}^{(i)},\sigma^{(i)})\) be the \((d_i,K_i,(\varepsilon')^2)\)-weighted pseudorandom reduction from \(\mathcal{P}_{(n_{i},s_{i})}\) to \(\mathcal{P}_{(n_{i+1},s_{i+1})}\), which is guaranteed by Lemma 18. The reduction has the following parameters:

1. \(d_i=O(\log^3 n_{i})\),

2. \(K_i=2^{\log^3 n_i}\),

3. \(s_{i+1}=s_{i}+O(\frac{\log(1/\varepsilon')}{\log n_{i}}+\log n_{i}\log \log n_{i})=s_{i}+O(\frac{\log(1/\varepsilon)}{\log n_{i}})\).

Using 2, we first composite \((\mathsf{R}^{(1)},\sigma^{(1)}),\ldots,(\mathsf{R}^{(l)},\sigma^{(l)})\) to get a \((d^*,K^*,\varepsilon^*)\)-weighted pseudorandom reduction \((\mathsf{R}^{(*)},\sigma^{(*)})\) from \(\mathcal{P}_{(n_0,s_0)}\) to \(\mathcal{P}_{(n_l,s_l)}\) with \(\mathsf{R}^{(*)}=\mathsf{R}^{(1)}\circ \ldots \circ \mathsf{R}^{(l)}\) and \(\sigma^{(*)}=\sigma^{(1)}\cdot \ldots \cdot \sigma^{(l)}\). We have the following parameters:

1. \(d^*=d_1+\ldots+d_l\leq O(l\log^3 n_1)\leq O(\log^{0.1}(n/\varepsilon))\),

2. \(K^*=K_1\cdot \ldots \cdot K_l\leq 2^{O(l\cdot \log^3n_1)}\leq 2^{O(\log^{0.1}(n/\varepsilon))}\),

3. \(\varepsilon^*=\sum_{i=1}^{l}(\varepsilon')^{2}\cdot \prod_{j=0}^{i-1}K_j\leq(\varepsilon')^{2}\cdot K^*\cdot l\leq \varepsilon'/2\),

4. \(s_l=s_0+\sum_{i=1}^{l}(s_i-s_{i-1})=s_0+\sum_{i=1}^{l}O(\frac{\log(1/\varepsilon')}{\log n_{i}})=s_0+O(\log 1/\varepsilon')\).

The first three items are attained by directly plugging in our parameters. The last item holds because \(n_i\) decreases rapidly. Note that \(n_{i-1}= 2^{\sqrt[3]{n_i}}\), and when \(n_i\geq 2^{15}=32768\), we have \(n_{i-1}\geq n^2_i\). When \(n_l\geq 32768\), it holds that \(\sum_{i=1}^{l}\frac{\log(1/\varepsilon')}{\log n_{i}}\leq \log 1/\varepsilon'\cdot (1/\log n_l+1/(2\log n_l)+1/(4\log n_l)+\cdots +1/(2^l\log n_l))\leq \log 1/\varepsilon'\).

Finally, we composite \((\mathsf{R}^{(*)},\sigma^{(*)})\) with \((\mathsf{R}^{(0)},\sigma^{(0)})\) to get the final reduction \((\mathsf{R},\sigma)\) from \(\mathcal{P}_{(n,s)}\) to \(\mathcal{P}_{(O(1),s_l))}\). By 1, the parameters are:

1. \(d=d^*+d_0=O(\log n\sqrt{\log(1/\varepsilon)})\),

2. \(K=K^*\cdot K_0\leq 2^{O(\log n\sqrt{\log(1/\varepsilon)})}\),

3. \(\varepsilon=\varepsilon/2+\varepsilon'/2\cdot K_0\leq \varepsilon\),

4. \(s=s_l=s_0+O(\log 1/\varepsilon')=s+O(\log n(\log\log n+\sqrt{\log(1/\varepsilon)})+\log(1/\varepsilon))\).

 ◻

Proof. Let \((\mathsf{R}, \sigma)\) be the reduction from Lemma 19. We construct the WPRG \((G,\sigma)\) with the same weight function \(\sigma\), and \(G\) is defined as \(G(x,i)=\mathsf{R}(x,i)\). By 19, to fool the original ROBP we only need to provide randomness for the seed of \((\mathsf{R},\sigma)\) and also provide a random string \(x\) which can fool an arbitrary ROBP in \(\mathcal{P}_{(O(1),s+O(\log n(\log\log n+\sqrt{\log(1/\varepsilon)})+\log(1/\varepsilon)))}\). We can use another \(\varepsilon\) error INW generator from [29] to generate this constant length \(x\) and this only takes \(s + O\left(\log n\left(\log\log n+\sqrt{\log(1/\varepsilon)}\right)+\log(1/\varepsilon) \right)\) random bits. Also the randomness used by \((\mathsf{R},\sigma)\) is \(O(\log n\sqrt{\log(1/\varepsilon)})\). So the total seed length is as stated. The weight also directly follows from 19. ◻

Proof. \(P'\) has the same vertex set as that of \(P\). The algorithm visits each layer \(i\) of \(P\) in the order \(i = 0, 1, 2, \ldots, n\). For layer \(i\), consider the subgraph \(S\) between \(V_i\) and \(V_{i+1}\). The algorithm visits each node \(v \in V_i\) in order. For each \(v \in V_i\), it tests if \(v\) can be reached by any previously visited node of \(V_i\) in \(S\). This can be done by revisiting each previous node \(v'\) and go through the cycle that \(v'\) is in. If none of the previous node can reach \(v\), then do the following traverse in \(S\). Starting from \(v\), choose an edge with label \(0\), and then go to the corresponding neighbor. For each next node \(u\) visited, denote \(\ell\) as the label of the adjacent edge through which we reach \(u\). If the other adjacent edge \(e'\) of \(u\) has a label \(\ell'\) such that \(\ell' = \ell\), then flip the label \(\ell'\). After this we traverse through \(e'\) to go to the next neighbor. Go on doing this until it reaches \(v\) again.

Notice that starting from \(v\) the traverse can go through every node of \(V_i \cup V_{i+1}\) reachable from \(v\). Because for each next neighbor \(u\), it can only be either \(v\) or a node which is not touched before in this traverse. In other words, this traverse is going through the cycle of \(S\) containing \(v\). Also note that after this traverse, every node reachable from \(v\), because of the flipping, can have different labels for its two adjacent edges. So after we visited every \(v \in V_i\), every node of \(S\) reachable by nodes in \(V_i\) has its two adjacent edges with different labels because of the flips. Hence the graph with these new labels is a permutation. The acceptance probability maintains the same since the edges are the same as before except that we flip some edge labels. After flippings, each node still has its two outgoing edges with different labels.

The traverse can be done in logspace since recording the index of a layer takes space \(O(\log n)\), recording the index of a node in a layer takes space \(O(\log w)\), and going through a cycle of \(S\) takes space \(O(\log w)\). ◻

Proof of 17. Let \(f\in \mathcal{R}^{tw}_{n,w,s}\) be the regular ROBP to derandomize. Let \(\ell \in \mathbb{N}\) be the number of iterations we need to perform and let \(\tau_i,\varepsilon_i\) be the error parameters of the \(i\)-th iteration for every \(i\in [\ell]\). The exact values of \(\ell,\{\tau_i,\varepsilon_i\}_{i\in [\ell]}\) will be specified later. For each iteration \(i\in [\ell]\), define the error reduction exponent \(k_i = \lceil \log_{1/\tau_i} (2/\varepsilon_i)\rceil\), and we setup \(n_i,K_i\) iteratively. Let \(n_0=n\). Consider every \(i\in [\ell]\). Let \(n_i = t, K_i = K\), where \(t=O(k_{i}\cdot \log n_{i-1})\) and \(K=O((2n_{i-1})^{k_i})\) are the parameters whose existence is guaranteed by 16, when initiating 16 with \(n = n_{i-1}, k = k_i, \tau = \tau_i\).

We iteratively define \(f_{i_1,i_2,\ldots,i_p}\in \mathcal{R}^{tw}_{n_p,w,s_p}\) for every \(i_1\in [K_1], i_2\in [K_2],\ldots,i_p\in [K_p]\) and \(p\in \{0,1,\ldots,\ell\}\) as follows:

1. When \(p=0\), \(f_{i_1,i_2,\ldots,i_p}\) is defined to be \(f\).

2. For every \(p\in [\ell]\), assume we have defined \(f_{i_1,i_2,\ldots,i_{p-1}}\). We denote \(\mathbf{M}^{(i_1,i_2,\ldots,i_{p-1})}_{l\ldots r}\) to be the stochastic matrix of \(f_{i_1,i_2,\ldots,i_{p-1}}\) from layer \(l\) to layer \(r\). For every \(0\leq l<r\leq n_{p-1}\), let \(\widetilde{G}^{(i_1,i_2,\ldots,i_{p-1})}_{l\ldots r}\) be a regular bigraph with a two-way labeling obtained by approximating \(\mathbf{M}^{(i_1,i_2,\ldots,i_{p-1})}_{l\ldots r}\) by the algorithm of 21 with error parameter \(\tau_p\) ⁸. Let \(\widetilde{\mathbf{M}}^{(i_1,i_2,\ldots,i_{p-1})}_{l\ldots r}\) be the stochastic matrix of \(\widetilde{G}^{(i_1,i_2,\ldots,i_{p-1})}_{l\ldots r}\). By 16, for every \(i_p\in [K_p]\) we have a partition \(0=m^{(p)}_{i_p,0}<m^{(p)}_{i_p,1}<\cdots<m^{(p)}_{i_p,n_p}=n_{p-1}\) and weights \(\sigma^{(p)}_{i_p}\in\{-1,0,1\}\) such that \[\label{def:f95i1i2} \begin{align} &\sum_{i_p\in [K_p]} \sigma^{(p)}_{i_p} \widetilde{\mathbf{M}}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,0}\ldots m^{(p)}_{i_p,1}}\widetilde{\mathbf{M}}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,1}\ldots m^{(p)}_{i_p,2}}\cdots \widetilde{\mathbf{M}}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,n_p-1}\ldots m^{(p)}_{i_p,n_p}} \text{ approximates }\\ &\mathbf{M}^{(i_1,i_2,\ldots,i_{p-1})}_{0\ldots n_{p-1}} \text{ with entry-wise error } \tau_p^{k_p}. \end{align}\tag{1}\]

   We define \(f_{i_1,i_2,\ldots,i_p}\) to be the concatenation of \(\widetilde{G}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,0}\ldots m^{(p)}_{i_p,1}}, \widetilde{G}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,1}\ldots m^{(p)}_{i_p,2}}, \ldots, \widetilde{G}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,n_p-1}\ldots m^{(p)}_{i_p,n_p}}\), which also has a two-way labeling.

Having defined the regular ROBPs, we use \(|\Sigma_p|=2^{s_p}\) to denote the alphabet size of \(f_{i_1,i_2,\ldots,i_p}\). Note that for every \(i_1\in [K_1], i_2\in [K_2],\ldots,i_p\in [K_p]\) and \(p\in \{0,1,\ldots,\ell\}\), it holds that \(f_{i_1,i_2,\ldots,i_p}\) always has the same alphabet size, since all such regular ROBPs are constructed from 15 with the same set of parameters.

Our derandomization algorithm computes \[\begin{align} &\sum_{i_1\in [K_1],i_2\in [K_2],\ldots,i_\ell\in [K_\ell]} \sigma^{(1)}_{i_1}\sigma^{(2)}_{i_2}\cdots \sigma^{(\ell)}_{i_\ell} \cdot \mathbb{E}_{x\in (\{0,1\}^{s_\ell})^{n_\ell}} f_{i_1,i_2,\ldots,i_\ell}(x). \end{align}\] The algorithm operates as follows, assuming we can access the ROBP \(f_{i_1,i_2,\ldots,i_\ell}\) with two-way labeling:

1. Enumerate all tuples \((i_1,i_2,\ldots,i_\ell)\in [K_1]\times [K_2]\times \cdots \times [K_\ell]\) and every string \((x_1,x_2,\ldots,x_{n_\ell})\in (\Sigma_\ell)^{n_\ell}\). For each tuple \((i_1,i_2,\ldots,i_\ell,x_1,x_2,\ldots,x_{n_\ell})\), we compute the following:

   1. Let \(u\in [w]\) be the starting vertex of \(f_{i_1,i_2,\ldots,i_\ell}\).

   2. For every \(t\in [n_\ell]\), we compute the rotation map \(u\gets \mathsf{Rot}_{f_{i_1,i_2,\ldots,i_\ell}}(u,x_t)\). (\(\mathsf{Rot}\) outputs a new pair \((u,x_t)\), but we discard \(x_t\).)

   3. If \(u\) is an accepting vertex of \(f_{i_1,i_2,\ldots,i_\ell}\), then add \(\sigma^{(1)}_{i_1}\sigma^{(2)}_{i_2}\cdots \sigma^{(\ell)}_{i_\ell}/(2^{n_l\cdot s_l})\) to the result; otherwise, add \(0\) to the result.

2. Return the result.

Since we do not have a direct access to \(f_{i_1,i_2,\ldots,i_\ell}\), we need to compute it with a recursive program. For every \(p\in [\ell]\) all tuples \((i_1,i_2,\ldots,i_p)\in [K_1]\times [K_2]\times \cdots \times [K_p]\) we compute \((u',x')\gets \mathsf{Rot}_{f_{i_1,i_2,\ldots,i_p}}(u,x)\) with the following recursive program, under the assumption that we have already defined the program to compute \(\mathsf{Rot}_{f_{i_1,i_2,\ldots,i_{p-1}}}(\cdot,\cdot)\):

1. If \(p=0\), then we compute \(\mathsf{Rot}_f(u,x)\) directly with the original ROBP \(f\).

2. Otherwise, assume \(u=(a,b)\) is the \(a\)-th vertex in the \(b\)-th layer of the ROBP \(f_{i_1,i_2,\ldots,i_p}\). Then we let \(b'\gets b+1\) and compute \((a',x')\gets \mathsf{Rot}_{\widetilde{G}^{(i_1,i_2,\ldots,i_{p-1})}_{m^{(p)}_{i_p,b}\ldots m^{(p)}_{i_p,b+1}}}(a,x)\) with \(\operatorname{DerandWalk}\) from 25:

   1. Let \(l\gets m^{(p)}_{i_p,b}, r\gets m^{(p)}_{i_p,b+1}\).

   2. Let \((a',x')\gets \operatorname{DerandWalk}(\tau_p,f_{i_1,i_2,\ldots,i_{p-1}},l,r,a,x)\), during which the algorithm calls \(\mathsf{Rot}_{f_{i_1,i_2,\ldots,i_{p-1}}}\).

   3. Let \(u'\gets (a',b')\).

   4. Output \((u', x')\).

We now examine both the error bound and the complexity of the algorithm. First we bound the error of the algorithm. By the construction of \(f_{i_1,i_2,\ldots,i_p}\), we have \[\begin{align} \left|\mathbb{E}_{x} f_{i_1,i_2,\ldots,i_{p-1}}(x) - \sum_{i_p\in [K_p]} \sigma^{(p)}_{i_p} \mathbb{E}_{y} f_{i_1,i_2,\ldots,i_p}(y)\right| &\leq \tau_p^{k_p} w \leq \varepsilon_p w \end{align}\] for every \(i_1\in [K_1], i_2\in [K_2],\ldots,i_{p-1}\in [K_{p-1}]\). Using triangular inequalities, we have the following bound: \[\begin{align} &\left|\mathbb{E}_{x} f(x) - \sum_{i_1\in [K_1],i_2\in [K_2],\ldots,i_\ell\in [K_\ell]} \sigma^{(1)}_{i_1}\sigma^{(2)}_{i_2}\cdots \sigma^{(\ell)}_{i_\ell} \cdot \mathbb{E}_{y} f_{i_1,i_2,\ldots,i_\ell}(y)\right|\\ &\leq \sum_{p=0}^{\ell-1} \sum_{i_1\in [K_1],i_2\in [K_2],\ldots,i_p\in [K_p]} \left|\mathbb{E}_{x} f_{i_1,i_2,\ldots,i_p}(x) - \sum_{i_{p+1}\in [K_{p+1}]} \sigma^{(p+1)}_{i_{p+1}} \mathbb{E}_{y} f_{i_1,i_2,\ldots,i_p,i_{p+1}}(y)\right|\\ &\leq \varepsilon_1 w + K_1\cdot \varepsilon_2 w + K_1K_2\cdot \varepsilon_3 w + \cdots + K_1K_2\cdots K_{\ell-1}\cdot \varepsilon_\ell w \end{align}\]

For the complexity of the algorithm, notice that the recursive algorithm computing \(\mathsf{Rot}_{f_{i_1,i_2,\ldots,i_p}}\) requires \((s_p-s_{p-1})+\log n_p\) more bits than that of the algorithm computing \(\mathsf{Rot}_{f_{i_1,i_2,\ldots,i_{p-1}}}\), since it only needs to store \(b_l,b_r\) and the current \(e_1,e_2,\ldots,e_{\log \left\lceil n_{p-1}\right\rceil}\) during the computation of \(((a,b),y) \gets \mathsf{Rot}_{f_{i_1,i_2,\ldots,i_{p-1}}}((a,b),y)\). Given that the base case \(p=0\) requires \(O(\log n_0 + s_0 + \log w)\) bits of space, the algorithm to compute \(\mathsf{Rot}_{f_{i_1,i_2,\ldots,i_\ell}}\) requires \(O(\sum_{p=0}^{\ell} \log n_p + s_\ell + \log w)\) bits of space. The main algorithm to compute the expectation of \(f_{i_1,i_2,\ldots,i_\ell}\) requires \(O(s_\ell +\sum_{p=0}^{\ell} \log K_p + \log w)\) bits to store the current tuple \((i_1,i_2,\ldots,i_\ell)\) and the current string \((x_1,x_2,\ldots,x_{n_\ell})\) and maintain the result. Therefore, the total space complexity of the algorithm is \[\begin{align} O\left(\sum_{p=0}^{\ell} \log n_p + s_\ell + \log w + \sum_{p=0}^{\ell} \log K_p\right). \end{align}\]

We conclude the proof by setting up the parameters \(\ell,\{\tau_i,\varepsilon_i\}_{i\in [\ell]}\). We set \(\varepsilon_1=\varepsilon/(2w),k_1=\lceil \log_{1/\tau_1} (2/\varepsilon_1)\rceil=\sqrt{\log(2w/\varepsilon)}\) and \(\tau_1=\min\{\frac{\varepsilon_1^{2/(k_1+1)}}{16\log^2 n_0},\frac{1}{64\log^2 n_0}\}\). Then \(n_1=O(\log n \sqrt{\log(w/\varepsilon)}),K_1=n^{O(\log n \sqrt{\log(w/\varepsilon)})}\). For every \(i\in \{2,\ldots,\ell-1\}\), we set \(\varepsilon_i=\varepsilon/(2wK_1)^2, k_i= O(\log^2 n_{i-1})\) and \(\tau_i=\min\{\frac{\varepsilon_{i-1}^{2/(k_i+1)}}{16\log^2 n_{i-1}},\frac{1}{64\log^2 n_{i-1}}\}\). \(k_i\) is chosen such that \(n_i=O(k_i\log n_{i-1})=\log^3 n_{i-1}\) and \(K_i=O((2n_{i-1})^{k_i})=n^{O(\log^3 n_{i-1})}\). We set \(\ell\) to be the smallest integer such that \(n_\ell\leq 32768\). We can easily verify that \(\ell =o(\log\log n)\). Given the parameters, the construction of 21 gives \(s_{i}=s_{i-1}+O(\log n_i(\log\log n_i + \log \tau_i))\) for every \(i\in [\ell]\). Therefore, \(s_1=s+O(\log n (\log\log n + \sqrt{\log(w/\varepsilon)}))\) and \(s_i=s_{i-1}+O(\frac{\log(wK_1/\varepsilon)}{\log n_{i-1}})\) for every other \(i\in [\ell]\).

Plugging the parameters into the error bound, we have \[\begin{align} &\left|\mathbb{E}_{x} f(x) - \sum_{i_1\in [K_1],i_2\in [K_2],\ldots,i_\ell\in [K_\ell]} \sigma_{i_1}\sigma_{i_2}\cdots \sigma_{i_\ell} \cdot \mathbb{E}_{y} f_{i_1,i_2,\ldots,i_\ell}(y)\right|\\ \leq &\varepsilon_1 w + K_1\cdot \varepsilon_2 w + K_1K_2\cdot \varepsilon_3 w + \cdots + K_1K_2\cdots K_{\ell-1}\cdot \varepsilon_\ell w\\ \leq &\varepsilon/2 + \ell \cdot K_1K_2\cdots K_{\ell-1} \cdot \frac{\varepsilon}{2wK_1^2} \cdot w \leq \varepsilon, \end{align}\] by noticing that \(K_1 K_2 \cdots K_{\ell-1} \le K^2_1\).

Plugging the parameters also gives the space complexity of the algorithm as \[\begin{align} &O\left(\sum_{i=0}^{\ell} \log n_i + s_\ell + \log w + \sum_{i=0}^{\ell} \log K_i\right)\\ =& O\left( s+\log n \left(\log\log n + \sqrt{\log(w/\varepsilon)} \right) + \log (w/\varepsilon) \right). \end{align}\] ◻

Proof. Let \(f\in \mathcal{B}_{(n,s,w)}\). Let \(X\) and \(Y_1,\ldots,Y_n\) be independent uniform random variables. We use a hybrid argument. Define \(U_i\) to be independent uniform random variables of length \(s\) for each \(i\in [n]\). Define \(Z_i=\mathrm{E\mathrm{\small xt}}(X,Y_i)\) for each \(i\in [n]\). Define \(R_i\) to be the random variable over \(V_i\), which represents the distribution of the state of \(f\) on input \(U_1,\ldots,U_i\). Define \(\widetilde{R}_i\) to be the random variable over \(V_i\) which represents the distribution of the state of \(f\) on input \(Z_1,\ldots,Z_i\). We will show that \(d_{TV}(R_i,\widetilde{R}_i)\leq \frac{i\cdot \varepsilon}{n}\) for all \(i\in [n]\).

The base case \(i=0\) is trivial, as both \(R_0\) and \(\widetilde{R}_0\) represent the initial state of \(f\). Assume the statement holds for \(i-1\). For the case \(i\), notice that \(|\text{supp}(\widetilde{R}_{i-1})|\leq w\leq 2^s\). By the chain rule 23, \[\tilde{H}_{\infty}(X|\widetilde{R}_{i-1})\geq 2s.\] Therefore 24 implies \[d_{TV}((Z_i,\widetilde{R}_{i-1}),(U_i,\widetilde{R}_{i-1}))\leq \frac{\varepsilon}{n}.\] By the data processing inequality, we have \[d_{TV}((U_i,\widetilde{R}_{i-1}),(U_i,R_{i-1}))\leq d_{TV}(\widetilde{R}_{i-1},R_{i-1})\leq \frac{(i-1)\varepsilon}{n}.\] Using the triangle inequality, we have \[d_{TV}((Z_i,\widetilde{R}_{i-1}),(U_i,R_{i-1}))\leq \frac{i\varepsilon}{n}.\] Denote the transition function of \(f\) from \(V_{i-1}\) to \(V_i\) as \(T_i\). Then \(\widetilde{R}_i=T_i(Z_i,\widetilde{R}_{i-1})\) and \(R_i=T_i(U_i,R_{i-1})\). Using the data processing inequality again, we have \[d_{TV}(R_i,\widetilde{R}_i)\leq d_{TV}((U_i,R_{i-1}),(Z_i,\widetilde{R}_{i-1}))\leq \frac{i\varepsilon}{n}.\] Therefore, \(d_{TV}(R_n,\widetilde{R}_n)\leq \varepsilon\) and the lemma is proved. ◻

Proof. \[\begin{align} \|L^{-1}-R(B,L,k)\|&=\left\lVert \left(I-\sum_{i=0}^{k}(I-BL)^{i}BL\right)L^{-1}\right\rVert\\ &=\left\lVert(I-BL)^{k+1}L^{-1}\right\rVert\\ &\leq \left\lVert I-BL\right\rVert^{k+1}\cdot \left\lVert L^{-1}\right\rVert\\ &\leq \left\lVert L^{-1}\right\rVert\cdot \left\lVert L\right\rVert^{k+1}\cdot \varepsilon_0^{k+1} \end{align}\] ◻

Proof. Define \(L\in \mathbb{R}^{(n+1)w\times (n+1)w}\) and \(B\in \mathbb{R}^{(n+1)w\times (n+1)w}\) as follows:

\[\begin{align} L&= \begin{pmatrix} I & 0 & 0 & \ldots & 0 & 0\\ -A_1 & I & 0 & \ldots & 0 & 0\\ 0 & -A_2 & I & \ldots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \ldots & -A_{n} & I\\ \end{pmatrix}, B= \begin{pmatrix} I & 0 & 0 & \ldots & 0 & 0\\ B_{0,1} & I & 0 & \ldots & 0 & 0\\ B_{0,2} & B_{1,2} & I & \ldots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ B_{0,n} & B_{1,n} & B_{2,n} & \ldots & B_{n-1,n} & I\\ \end{pmatrix} \end{align}\] This means that \[\begin{align} L^{-1}= \begin{pmatrix} I & 0 & 0 & \ldots & 0 & 0\\ A_1 & I & 0 & \ldots & 0 & 0\\ A_1A_2 & A_2 & I & \ldots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ A_1A_2\ldots A_{n} & A_2\ldots A_{n} & A_3\ldots A_{n} & \ldots & A_{n} & I\\ \end{pmatrix} \end{align}\]

By assumption, there exists a submultiplicative norm \(\|\cdot\|\) on \(\mathbb{R}^{w\times w}\). We induce a submultiplicative norm on \(\|\cdot\|_A\) on \(\mathbb{R}^{(n+1)w\times (n+1)w}\): Let \(M=(M_{i,j})_{i,j=1}^{n+1}\in \mathbb{R}^{(n+1)w\times (n+1)w}\), where each \(M_{i,j}\in \mathbb{R}^{w\times w}\). Define \(\|M\|_A=\max_{j\in [n+1]}\sum_{i=1}^{n+1}\|M_{i,j}\|\). It is easy to verify that \(\|\cdot\|_A\) is a submultiplicative norm, and \(\|M\|_A=\|M\|_1\) when \(w=1\).

Beacuse \(\|B_{i,j}-A_{i+1}\ldots A_j\|\leq \varepsilon/(n+1)^2\) for all \(i+1< j\), we have \(\|B-L^{-1}\|_A\leq \varepsilon\). Also, Because \(\|A_i\|\leq 1\) for all \(i\), we have \(\|L\|_A\leq 2\) and \(\|L^{-1}\|_A\leq n+1\).

Define \(M=R(B,L,(k-1)/2)\), then \[\begin{align} \|L^{-1}-M\|_A\leq \|L^{-1}\|_A\cdot\|L\|_A^{\frac{k+1}{2}}\cdot \left(\frac{\varepsilon}{n+1}\right)^{\frac{k+1}{2}}\leq \varepsilon^{(k+1)/2}\cdot(n+1). \end{align}\]

Expand \(M=(M_{i,j})_{i,j=1}^{n+1}\), where each \(M_{i,j}\in \mathbb{R}^{w\times w}\). We foucus on \(M_{1,n+1}\), which is a \(w\times w\) matrix and \(\|M_{1,n+1}-A_1A_2\ldots A_n\|\leq \|L^{-1}-M\|_A\leq \varepsilon^{(k+1)/2}\cdot(n+1)\).

To express \(M_{1,n+1}\), we define \[\begin{align} \Delta_{i,j}=\begin{cases} B_{i,j-1}A_j-B_{i,j} & i<j,\\ 0 & i\geq j. \end{cases} \end{align}\]

Then we have \[\begin{align} M_{1,n+1}=B_{0,n}+\sum_{j=1}^{(k-1)/2}\sum_{0<r_1<\cdots<r_j<n}\Delta_{0,r_1}\Delta_{r_1,r_2}\cdots \Delta_{r_{j-1},r_j}B_{r_j,n}. \end{align}\]

Defining \(M^{(0)}_{i,j}=B_{i,j-1}A_j=B_{i,j-1}B_{j-1,j}\) and \(M^{(1)}_{i,j}=B_{i,j}\), we have \[\begin{align} M_{1,n+1}=B_{0,n}+\sum_{j=1}^{(k-1)/2}\sum_{0<r_1<\cdots<r_j<n}\sum_{t_1,\ldots,t_j\in \{0,1\}}(-1)^{t_1+\cdots+t_j} M^{(t_1)}_{0,r_1}M^{(t_2)}_{r_1,r_2}\ldots M^{(t_j)}_{r_j,n}. \end{align}\]

Encoding \(j,r_1,\ldots,r_j,t_1,\ldots,t_j\) into a single index \(i\in[K]\), rewrite \(M^{(t_1)}_{0,r_1}M^{(t_2)}_{r_1,r_2}\ldots M^{(t_j)}_{r_j,n}\) as \(B_{0,n_{i,1}}B_{n_{i,1},n_{i,2}}\ldots B_{n_{i,k-1},n_{i,k}}\) for some \(n_{i,1}\leq \ldots\leq n_{i,k}=n\), define \(\sigma_i=(-1)^{t_1+\ldots+t_j}\), we have the desired result.

Finally, we bound \(K\) by \(\frac{k-1}{2}\cdot (n+1)^{(k-1)/2}\cdot 2^{(k-1)/2}\leq (8n)^{k+1}\). ◻

Proof. \[\begin{align} &\Pr_{x \in \{0,1\}^r }\left[\left\|2^{-p}\sum_{y\in \{0,1\}^p} f(\mathrm{Samp}(x,y)) - \mathbb{E}[f] \right\|_{1} \ge C \alpha w \right]\\ =&\Pr_{x \in \{0,1\}^r }\exists_{i\in [w]}\left[\sum_{j\in [w]} \left[2^{-p}\sum_{y\in \{0,1\}^p} f(\mathrm{Samp}(x,y))_{i,j} - \mathbb{E}[f]_{i,j} \right] \ge C \alpha w \right]\\ \leq&\Pr_{x \in \{0,1\}^r }\exists_{i\in [w],j\in [w]}\left[\left|2^{-p}\sum_{y\in \{0,1\}^p} f(\mathrm{Samp}(x,y))_{i,j} - \mathbb{E}[f]_{i,j} \right| \ge C \alpha \right]\\ \leq&\sum_{i\in [w],j\in [w]}\Pr_{x \in \{0,1\}^r }\left[\left|C^{-1}2^{-p}\sum_{y\in \{0,1\}^p} f(\mathrm{Samp}(x,y))_{i,j} - C^{-1}\mathbb{E}[f]_{i,j} \right| \ge \alpha \right]\\ \leq& w^2 \gamma. \end{align}\] ◻

Proof. Take any \(f\in \mathcal{B}_{(n,s,w)}\). Let \(A_i=\mathbb{E}f^{[i-1,i]}(G_0(U))\) for \(i\in [n]\). Define \(B_{i,j}=\frac{1}{2^p}\sum_{z\in \{0,1\}^d} w_0(z)\cdot f^{[i,j]}(G(z))\). For any \(x\in \{0,1\}^r\) and \(0\leq i<i+1<j\leq n\), we define \(B^x_{i,j}=\frac{1}{2^p}\sum_{y\in \{0,1\}^p} w_0(\mathrm{Samp}(x,y))\cdot f^{[i,j]}((G(\mathrm{Samp}(x,y)))_{j-i})\). For \(j=i+1\), we define \(B^x_{i,i+1}=A_i\) as the true transition matrix.

We call a seed \(x\) to be ‘good’ iff for all \(i,j\in [n]\), \(\|B_{i,j}-B^x_{i,j}\|_1\leq 1/(2w\cdot (n+1))\). Otherwise, we call \(x\) to be ‘bad’.

Since \(w_0\) is \(W\)-bounded, \(\|w_0(z)\cdot f^{[i,j]}(G(z))\|_1\) is at most \(W\). Note that \(W\alpha w\leq 1/(2w\cdot (n+1)^2)\). By Lemma [lem:matrix32sampler], for any \(i,j\in [n]\), \[\begin{align} \Pr_{x\in \{0,1\}^r}[\|B_{i,j}-B^x_{i,j}\|_1>1/(2w\cdot (n+1))]\leq w^2\gamma=\varepsilon/(2(2n)^k\cdot W^{k}). \end{align}\]

By a union bound, the probability \(\Pr_{x\in \{0,1\}^r}[x \text{ is bad}]\) is at most \(\varepsilon/(2(2n)^k\cdot W^{k})\).

For a good seed \(x\), we have \(\|A_i\ldots A_j-B^x_{i,j}\|_1\leq \|A_i\ldots A_j-B_{i,j}\|_1+\|B_{i,j}-B^x_{i,j}\|_1\leq 1/(w\cdot (n+1)^2)\). By Theorem 7, we have: \[\begin{align} \left\|A_1\cdots A_n-\sum_{i=1}^{k}\sigma_i B^x_{0,i_1}B^x_{i_1,i_2}\ldots B^x_{i_{k-1},i_k}\right\|_1 \leq ((n+1)w)^{-k}\cdot (n+1)\leq \varepsilon/2. \end{align}\]

For a bad seed, we can upper-bound \(\|B^x_{i,j}\|_1\) by \(K\). Therefore, we have: \[\begin{align} \left\|A_1\cdots A_n-\sum_{i=1}^{K}\sigma_i B^x_{0,i_1}B^x_{i_1,i_2}\ldots B^x_{i_{k-1},i_k}\right\|_1 \leq 1+K\cdot W^k \end{align}\]

Combining the two cases, we have the following inequality: \[\begin{align} &\left|\mathbb{E}f- \frac{1}{K\cdot 2^{kp+r}}\sum_{x\in \{0,1\}^r}\sum_{y_1,\ldots,y_{k}\in \{0,1\}^p}w(x,y_1,\ldots,y_{k},i)f(G(x,y_1,\ldots,y_{k}))\right|\\ \leq&\left\|A_1\cdots A_n-\frac{1}{2^r}\sum_{x\in \{0,1\}^r}\sum_{i=1}^{K}\sigma_i B^x_{0,i_1}B^x_{i_1,i_2}\ldots B^x_{i_{k-1},i_k}\right\|_1\\ \leq&\frac{1}{2^r}\sum_{\substack{x\in \{0,1\}^r \\ x \text{ is bad}}}\left\|A_1\cdots A_n-\sum_{i=1}^{K}\sigma_i B^x_{0,i_1}B^x_{i_1,i_2}\ldots B^x_{i_{k-1},i_k}\right\|_1\\ &+\frac{1}{2^r}\sum_{\substack{x\in \{0,1\}^r \\ x \text{ is good}}}\left\|A_1\cdots A_n-\sum_{i=1}^{K}\sigma_i B^x_{0,i_1}B^x_{i_1,i_2}\ldots B^x_{i_{k-1},i_k}\right\|_1\\ \leq&\varepsilon/2+(1+K\cdot W^k)\cdot\gamma\\ \leq&\varepsilon. \end{align}\]

The resulting generator uses \(r+kp+ks\) random bits in total: \(r\) bits for the sampler seed, \(p\) bits for each of the \(k\) sampler queries, and \(s\) bits for each of the \(k\) one-step transitions.

The lemma follows. ◻

Proof. The proof is by induction on \(t\). For the base case \(t=0\), both sides mean \(u\) has an outgoing edge labeled \(x\) going to \(v\). Assume the statement holds for \(t-1\). Recall that \[\widetilde{G}_{ j \to j+2^t} = \widetilde{G}_{ j \to j+2^{t-1}} \textcircled{p}_{H_t} \widetilde{G}_{j+2^{t-1}\to j+2^t}, \forall t \ge 1,\] Then for \(t\), the left side can be computed as follows (where \(x=(z,y)\)): \[\begin{align} &(w,z)=\mathsf{Rot}_{\widetilde{G}_{j,j+2^{t-1}}}(u,z),\\ &(z',y')=\mathsf{Rot}_{H_t}(z,y),\\ &(v,w)=\mathsf{Rot}_{\widetilde{G}_{j+2^{t-1},j+2^t}}(z',y'). \end{align}\] Where the right side can be computed as follows: \[\begin{align} &f^{[j,j+2^{t-1}]}(\mathsf{INW}_{t-1}(z))=w,\\ &H_t[z,y]=z',\\ &f^{[j+2^{t-1},j+2^t]}(\mathsf{INW}_{t-1}(z'))=v. \end{align}\] The induction hypothesis implies that the two sides are equivalent. ◻

Proof. Let \(\lambda=\min\{\varepsilon/(11\log n),1/6(\log^2 n)\}\). Let \(d=2^s\) and for each \(t\in [\log n]\), let \(H_t\) be a \(c\)-regular expanders with \(\lambda(H_t)\leq \lambda\) from 22. Let \(\{\mathsf{INW}_t\}_{t\in [\log n]}\) be the INW generator from the definition. Let \(\mathsf{INW}=\mathsf{INW}_{\log n}\). Then \(\mathsf{INW}\) is a PRG with seed lengths \[\log d+t\cdot \log c=s+O(\log n(\log\log n+\log(1/\varepsilon))).\]

For any \(f\in \mathcal{P}_{(n,s)}\), the derandomized product of \(f\) coincides with the the output of \(f\circ INW\), i.e. \(\widetilde{\mathbf{W}}_{n\gets 0}=E_X f^{[0,n]}(\mathsf{INW}(X))\). Since \(\widetilde{\mathbf{W}}_{n\gets 0}\overset{sv}{\approx}_{11\lambda\log n} \widetilde{\mathbf{W}}_{n\gets n-1}\cdots \widetilde{\mathbf{W}}_{1\gets 0}\) by 21, \(INW\) fools \(f\) with \(\varepsilon\)-sv-error. ◻

Proof. \[\begin{align} \mathsf{W}(f,0,n,y_{acc})&=\sum_{i=1}^n \mathsf{W}(f,i,\mathbf{M}_{i\ldots n} y_{acc})=\sum_{i\in [n]}\sum_{(u,v)\in{E_{i-1,i}}}\left|e_u^T \mathbf{M}_{i-1\ldots n}y_{acc}-e_v^T \mathbf{M}_{i\ldots n} y_{acc}\right|\\ &=\sum_{(u,v)\in E}\left|\mathbb{E}[f^{u\to}-f^{v\to}]\right|=\mathsf{W}(f) \end{align}\] ◻

Proof of 11. Set \(k=O(\sqrt{\log (1/\varepsilon)})\). Set \(\tau=\frac{\varepsilon^{1/k}}{30\log n\cdot \mathsf{W}(f))}\). Let \(\mathsf{PRG}:\{0,1\}^d\to (\{0,1\}^s)^n\) be the \(\tau\)-PRG given by 35 and let \((\mathsf{PRG}(\cdot))_{m}\) denote its first \(m\) symbols over \(\{0,1\}^s\). we define \(\mathbf{M}^{(0)}_{l\ldots r}:=\mathbb{E}_{x\in\{0,1\}^d}f^{[l,r]}((\mathsf{PRG}(x))_{r-l})\) and expand \(\mathbf{M}^{(k)}_{0\ldots n}\) as a weighted sum of products of \(\mathbf{M}^{(0)}_{l\ldots r}\), we get the following sum: \[\mathbf{M}^{(k)}_{0\ldots n}=\frac{1}{K}\sum_{i\in K}\gamma_i\cdot \mathbf{M}^{(0)}_{m_{i,0}\ldots m_{i,1}}\mathbf{M}^{(0)}_{m_{i,1}\ldots m_{i,2}}\ldots \mathbf{M}^{(0)}_{m_{i,t-1}\ldots m_{i,t}},\] where \(\gamma_i\in\{-K,K\}\) are weights and \(0=m_{i,0}\leq m_{i,1}\leq \cdots\leq m_{i,t}=n\) are partitions of \([n]\). We set the \((\log K,K,\varepsilon)\)-reduction \((\mathsf{R},\sigma)\) from \(\mathcal{R}_{n,s,w}\) to \(\mathcal{B}_{t,d,w}\) as \[\begin{align} \mathsf{R}(x_1,x_2,\cdots,x_t,i)&=((\mathsf{PRG}(x_1))_{m_{i,1}-m_{i,0}},(\mathsf{PRG}(x_2))_{m_{i,2}-m_{i,1}},\cdots,(\mathsf{PRG}(x_t))_{m_{i,t}-m_{i,t-1}}),\\ \sigma(i)&=\gamma_i. \end{align}\]

By 35, \(\forall y\in \mathbb{ R}^w,\left\|\left(\mathbf{M}^{(0)}_{l\ldots r} -\mathbf{M}_{l\ldots r}\right)y\right\|_\infty\leq \frac{\varepsilon^{1/k}}{30\log n}\cdot \frac{\mathsf{W}(f,l,r,y)}{\mathsf{W}(f)}\). Then by 19, \(\left\|\left(\mathbf{M}^{(k)}_{0\ldots n} -\mathbf{M}_{0\ldots n}\right)y_{acc}\right\|_\infty\leq \varepsilon\cdot \frac{\mathsf{W}(f,0,n,y_{acc})}{\mathsf{W}(f)}= \varepsilon\), which indicates that our reduction achieves the target precision.

Given the construction of the error reduction polynomial, one can find \(K=n^{O(k)}=2^{O(\log n\sqrt{\log(1/\varepsilon)})}\) and \(t=O(k\log n)=O(\log n\sqrt{\log(1/\varepsilon)})\). Also, 35 indicates \(d=s+O(\log n(\log\log n+\log w+\log(\mathsf{W}(f))+\sqrt{\log(1/\varepsilon)})\). That completes the proof. ◻

Proof. We use 21 for \(\mathcal{B}_{(n,s,w)}\) with error \(\varepsilon_0=\frac{2^{-4\log n}}{(n+1)^2}\). By 21, the seed length is \(s+O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}\right)\). Then we can set \(k=\frac{\log (n/\varepsilon)}{\log n}\geq \frac{2\log((n+1)/\varepsilon)}{\log(1/((n+1)^2\varepsilon_0))}\) in Lemma 6 and invoke it. This gives a reduction of error \((\varepsilon_0(n+1)^2)^\frac{k+1}{2}\cdot(n+1)\leq \varepsilon\). ◻

Proof. Fix \(c\) to be a constant. We use 21 for \(\mathcal{B}_{(n,s,w)}\) with error \(\varepsilon_0=\frac{2^{-\frac{4\log w}{n^{1/c}}}}{(n+1)^2}\). By 21, the seed length is \(s+O\left(\log(nw/\varepsilon_0)\cdot\frac{\log n}{\log\log w-\log\log(n/\varepsilon_0)}\right)= s+O\left(\log w\cdot\frac{\log n}{\log n^{1/c}}\right)=s+C' \log w\), where \(C'\) depends on \(c\). Then we can set \(k=n^{1/c}\cdot \frac{\log(n/\varepsilon)}{\log w} \ge \frac{\log(1/\varepsilon)+\log (n+1)}{1/2\cdot\log(1/((n+1)^2\varepsilon_0))}\) in Lemma 6 and invoke it. This gives a reduction of error \((\varepsilon_0(n+1)^2)^\frac{k+1}{2}\cdot(n+1)\leq \varepsilon\). ◻

Proof. We use 21 for \(\mathcal{B}_{(n,s,w)}\) with error \(\varepsilon_0=\frac{2^{-\frac{\log((n+1)/\varepsilon)}{\log^2 n}}}{(n+1)^2}\). The condition \(\varepsilon \leq 2^{-2\log^2n\log (nw)}\) guarantees that \(\log(nw/\varepsilon_0)\leq 2\log(1/\varepsilon_0)\).

By 21, the seed length is \(s+O(\left(\log(nw/\varepsilon_0)\cdot \log n\right))=s+O\left(\frac{\log (1/\varepsilon)}{\log n}\right)\). Then we can set \(k=10\log^2 n\geq \frac{\log((n+1)/\varepsilon)}{1/2\cdot \log(1/(n+1)^2\varepsilon_0)}\) in Lemma 6 and invoke it. This gives a reduction of error \((\varepsilon_0(n+1)^2)^\frac{k+1}{2}\cdot(n+1)\leq \varepsilon\). ◻

Proof. We do three stages of reductions: In the first stage, we reduce the length from \(n\) to \(n_0=\min\{n,\log(n/\varepsilon)/\log n\}\). Then we split the algorithm into two cases: if \(w> n/\varepsilon\), we reduce the length to \(\frac{\log w}{\log n/\varepsilon}\), then fool it with PRG; if \(w\leq n/\varepsilon\), we reduce the length to \(\left(\frac{10\log(n/\varepsilon)}{\log w}\right)^2\), then we further reduce the length to \(O(1)\) using a different parameter scheme, and fool it with PRG.

For the first stage, if \(n\leq \frac{\log(n/\varepsilon)}{\log n}\), then the goal is already achieved, and we set \(n_0=n\). Otherwise, we use 36 to reduce the length from \(n\) to \(\frac{\log(n/\varepsilon)}{\log n}\) via a \((\log K,K, \varepsilon/2)\)-weighted pseudorandom reduction, where \(K\leq n^2/\varepsilon^2\). Recall that the number of reduced ROBPs is \(K\). The reduced ROBPs have length \(n_0=\frac{\log(n/\varepsilon)}{\log n}\), width \(w\), and alphabet bit-length \[s_0=s+O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}\right).\]

We set \(\varepsilon'=\varepsilon/2K^2\) which will serve as the error parameter for the remaining stages.

1. Case \(w>n/\varepsilon\): We iteratively use 37 for \(l\) times (\(l\) will be defined later): In iteration \(0\leq i\leq l\), we reduce the length from \(n_i\) to \(n_{i+1}=n_i^{1/4}\frac{\log(n_iw/\varepsilon')}{\log w}\leq 4n_i^{1/4}\), decomposing one ROBP into \(K_i\) shorter ones and increasing the alphabet bit-length from \(s_i\) to \(s_{i+1}\). Parameter calculation shows \[s_{i+1}=s_i+C\log w, \qquad K_i\leq (8n_i)^{\frac{\log(n_i/\varepsilon')}{\log w}n_i^{1/4}+1}\leq (n/\varepsilon)^{\frac{2n_i^{1/4}\log n_i}{\log w}}\leq (n/\varepsilon)^{1/\log^{1/4} w},\] where the first inequality is directly due to 37 and the second inequality follows from \(n_i\leq n_0=\log(1/\varepsilon)/\log n\leq \log^2w\).

   The iteration goes until \(n_l\leq \frac{\log w}{\log n/\varepsilon'}\), which continues for at most \(l=\log\log n_l-\log\log n'\leq \log\log\min\{n,\log w\}-\log\log\frac{\log w}{\log n/\varepsilon}\) rounds. When the iteration stops, the reduced ROBPs of length \(n_l\) and alphabet bit-length \(s_l\) could be \(\varepsilon'\)-fooled by Chen-Ta-Shma PRG with seed-length \(s_l+O\left(\log(nw/\varepsilon')\cdot \frac{\log n_l}{\log\log w-\log\log(n_l/\varepsilon')}\right)=s_l+O(\log(nw/\varepsilon)\).

   To account for the total error introduced, we first bound the number of reductions we use in the second stage. We have \(l\) rounds of reductions, and in each round we have at most \(K\cdot \prod_{i=0}^{l} K_i\) parallel reductions. Therefore, the total amount of reductions we use is at most \(l\cdot K\cdot \prod_{i=0}^{l} K_i \leq K\cdot (n/\varepsilon)^{\frac{2\log\log w}{\log^{1/4} w}}\leq K^2\). The total error introduced in the second stages is at most \(K^2\cdot \varepsilon'=\varepsilon/2\). Together with the error \(\varepsilon/2\) introduced in the first stage, we have that the total error introduced is at most \(\varepsilon\).

   Then we bound the randomness we use. The randomness used in selecting the index of reductions is at most \(\log(K\cdot \prod_{i=0}^{l} K_i)\leq O(\log (nw/\varepsilon))\). The randomness used in fooling the final reduced ROBPs equals \(s_{l}+O(\log nw/\varepsilon')\). By the constructions, we introduce \(s_0-s=O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}\right)\) bits in the first stage, \(s_l-s_0=O(l\cdot \log w)\) bits, which is \(O\left(\log w \cdot \left(\log\log\min\{n,\log w\}-\log\log\frac{\log w}{\log n/\varepsilon}\right)\right)\) bits in the second stage. Therefore, the total randomness we use is at most \[s+O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}+\log w (\log\log\min\{n,\log w\}-\log\log\frac{\log w}{\log n/\varepsilon})+\log (1/\varepsilon)\right)\] as we claimed.

2. Case \(w\leq n/\varepsilon\): We will reduce the length to \(n'=\left(\frac{10\log(n/\varepsilon)}{\log w}\right)^2\). If \(n_0\leq n'\), the goal is already achieved and we directly go to the 3rd stage.

   Now consider \(n' < n_0\). One can deduce that \(\log(1/\varepsilon)\leq \log^2 w\log n\), since \(n_0 \leq \log(1/\varepsilon)/\log n\). We iteratively use 37 for \(l\) times (\(l\) will be defined later): In iteration \(0\leq i\leq l\), we reduce the length from \(n_i\) to \(n_{i+1}=n_i^{1/4}\frac{\log(n_iw/\varepsilon')}{\log w}\), decomposing one ROBP into \(K_i\) shorter ones and increasing the alphabet bit-length from \(s_i\) to \(s_{i+1}\). Notice that \(n_{i+1}< n_{i}^{3/4}\) when \(n_i\geq \left(\frac{\log(n_iw/\varepsilon')}{\log w}\right)^2\), which is always true when \(n_i\geq n'\). Parameter calculation shows \[s_{i+1}=s_i+C\log w, \qquad K_i\leq (8n_i)^{\frac{\log(n_iw/\varepsilon')}{\log w}n_i^{1/4}+1}\leq (nw/\varepsilon)^{\frac{2n_i^{1/4}\log n_i}{\log w}}\leq (nw/\varepsilon)^{1/\log^{1/4} w},\] where the first inequality is directly due to 37 and the second inequality follows from \(n_i\leq n_0=\log(1/\varepsilon)/\log n\leq \log^2w\). The iteration goes until \(n_l\leq n'\), which continues for at most \(l=\log\log n_l-\log\log n'\leq \log\log\min\{n,\log w\}\) rounds.

   Now we enter the third stage and we have that \(n'\leq \left(\frac{\log(1/\varepsilon')}{\log w}\right)^2\). Thus, \(\log(1/\varepsilon')\geq \log w \cdot \sqrt{n'}\geq \log(n'w)\cdot \log^2 n'\), enabling us to apply 38. We use an iterative approach: We set \(n'_0=n_l<n', s'_0=s_l\), and in iteration \(0\leq i\leq l'\), we reduce the length from \(n'_i\) to \(n'_{i+1}=10\log^2 n'_i\), decomposing one ROBP into \(K'_i\) shorter ones and increasing the alphabet bit-length from \(s'_i\) to \(s'_{i+1}\). Parameter calculation shows \[\begin{align} s'_{i+1}&=s'_i+O\left(\frac{\log (1/\varepsilon')}{\log n'_i}\right),\\ K'_i&\leq (8n'_i)^{10\log^2 n'_i+1}\\ &\leq (8n')^{10\log^2 n' + 1} \\ &\leq 2^{100\log^3 n' } \\ &\leq 2^{100\log^3 \log(1/\varepsilon')}\\ &\leq 2^{{100\log^3 \log(n/\varepsilon)}}\\ &\leq 2^{\frac{\log (n/\varepsilon)}{\log^{1/2}w}}\\ &\leq (n/\varepsilon)^{1/\log^{1/2} w}. \end{align}\] We stress that the sequence \(\log n_i\) decreases exponentially, making the sum \(\sum_{i=0}^{l'} O\left(\frac{\log (1/\varepsilon')}{\log n'_i}\right)\) dominated by a geometric series (i.e. \(\sum_{i=0}^{l'} O\left(\frac{\log (1/\varepsilon')}{2^{l'-i}\log n'_{l'}}\right)\)), and therefore the total increase of alphabet bit-length is at most \(O(\log (1/\varepsilon'))\). The iteration continues for at most \(l'=\log\log n'_l\leq \log\log \log (n/\varepsilon)\leq \log\log w\) rounds, until \(n'_{l'}\leq O(1)\) and we fool the final reduced ROBPs with Chen-Ta-Shma PRG with seed-length \(s'_{l'}+O(\log nw/\varepsilon')\).

   Overall, for this case, the total amount of reductions we use is at most \((l+l')\cdot K\cdot \prod_{i=0}^{l} K_i \cdot \prod_{i=0}^{l'} K'_i\leq K\cdot (n/\varepsilon)^{\frac{2\log\log w}{\log^{1/4} w}}\leq K^2\). The total error introduced in the second and third stages is at most \(K^2\cdot \varepsilon'=\varepsilon/2\). Together with the error \(\varepsilon/2\) introduced in the first stage, we have that the total error introduced is at most \(\varepsilon\).

   Then we bound the randomness we use. The randomness used in selecting the index of reductions is at most \(\log(K\cdot \prod_{i=0}^{l} K_i \cdot \prod_{i=0}^{l'} K'_i)\leq O(\log (nw/\varepsilon))\). The randomness used in fooling the final reduced ROBPs equals \(s'_{l'}+O(\log nw/\varepsilon')\). By the constructions, we introduce \(s_0-s=O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}\right)\) bits in the first stage, and \(s_l-s_0=O(l\cdot \log w)\) bits in the 2nd stage, which is \(O\left(\log w \cdot \log\log\min\{n,\log w\}\right)\). In the third stage, we introduce \(s'_{l'}-s_l=O(\log (1/\varepsilon'))=O(\log (n /\varepsilon))\) bits. Therefore, the total randomness we use is at most \[s+O\left(\frac{\log n\log (nw)}{\log\log w-\log\log n}+\log w \cdot\log\log\min\{n,\log w\}+\log (n /\varepsilon)\right)\] as we claimed.

 ◻