Implications of Better PRGs for Permutation Branching Programs

Doron, Dean; Hoza, William M.

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.28

Implications of Better PRGs for Permutation Branching Programs

Dean Doron

Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel William M. Hoza

Department of Computer Science, The University of Chicago, IL, USA

Abstract

We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let $c\in[1,2)$ be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width- $6$ length- $n$ permutation ROBPs with error $1/n$ and seed length $\widetilde{O}(\log^{c}n)$ , then there are explicit hitting set generators (HSGs) for width- $4$ length- $n$ ROBPs with threshold $1/\operatorname{polylog}(n)$ and seed length $\widetilde{O}(\log^{c}n)$ .

For context, there are known explicit PRGs that fool constant-width permutation ROBPs with error $\varepsilon$ and seed length $O(\log n\cdot\log(1/\varepsilon))$ (Koucký, Nimbhorkar, and Pudlák STOC 2011; De CCC 2011; Steinke ECCC 2012). When $\varepsilon=1/n$ , there are known constructions of weighted pseudorandom generators (WPRGs) that fool polynomial-width permutation ROBPs with seed length $\widetilde{O}(\log^{3/2}n)$ (Pyne and Vadhan CCC 2021; Chen, Hoza, Lyu, Tal, and Wu FOCS 2023; Chattopadhyay and Liao ITCS 2024), but unweighted PRGs with seed length $o(\log^{2}n)$ remain elusive. Meanwhile, for width- $4$ ROBPs, there are no known explicit PRGs, WPRGs, or HSGs with seed length $o(\log^{2}n)$ .

Our reduction can be divided into two parts. First, we show that explicit low-error PRGs for width- $6$ permutation ROBPs with seed length $\widetilde{O}(\log^{c}n)$ would imply explicit low-error PRGs for width- $3$ ROBPs with seed length $\widetilde{O}(\log^{c}n)$ . This would improve Meka, Reingold, and Tal’s PRG (STOC 2019), which has seed length $o(\log^{2}n)$ only when the error parameter is relatively large. Second, we show that for any $w$ , $n$ , $s$ , and $\varepsilon$ , an explicit PRG for width- $w$ ROBPs with error $0.01/n$ and seed length $s$ would imply an explicit $\varepsilon$ -HSG for width- $(w+1)$ ROBPs with seed length $O(s+\log n\cdot\log(1/\varepsilon))$ .

Keywords and phrases:

hitting set generators, pseudorandom generators, read-once branching programs

Category:

RANDOM

Funding:

William M. Hoza: Part of this work was done while the author was a graduate student at the University of Texas at Austin, supported by the NSF GRFP under grant DGE-1610403 and by a Harrington Fellowship from UT Austin. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pseudorandomness and derandomization

Acknowledgements:

We thank Omer Reingold and Avishay Tal for valuable discussions.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.28

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

One of the classic goals of computational complexity theory is to clarify the relationship between two fundamental computational resources: randomness and space complexity. The “ $\mathsf{L}=\mathsf{BPL}$ ” conjecture asserts that if a language can be decided by a randomized algorithm that uses $S$ bits of space and always halts, where $S\geq\log n$ , then it can also be decided by a deterministic algorithm that uses $O(S)$ bits of space. A particularly satisfying way to prove $\mathsf{L}=\mathsf{BPL}$ would be to design a suitable pseudorandom generator (PRG), defined next.

Definition 1.1 (PRGs).

Let $\mathcal{F}$ be a class of functions $f\colon\{0,1\}^{n}\to\mathbb{R}$ , let $\varepsilon>0$ , and let $X$ be a distribution over $\{0,1\}^{n}$ . We say that $X$ $\varepsilon$ -fools $\mathcal{F}$ , or fools $\mathcal{F}$ with error $\varepsilon$ , if

|\operatorname*{\mathbb{E}}[f]-\operatorname*{\mathbb{E}}[f(X)]|\leq\varepsilon.

Here $\operatorname*{\mathbb{E}}[f]$ is shorthand for $\operatorname*{\mathbb{E}}[f(U_{n})]$ , where $U_{n}$ denotes the uniform distribution over $\{0,1\}^{n}$ . An $\varepsilon$ -PRG for $\mathcal{F}$ , or a PRG that fools $\mathcal{F}$ with error $\varepsilon$ , is a function $G\colon\{0,1\}^{s}\to\{0,1\}^{n}$ such that $G(U_{s})$ fools $\mathcal{F}$ with error $\varepsilon$ . The parameter $s$ is called the seed length of the PRG.

To simulate a randomized algorithm, we would like a PRG that fools some model $\mathcal{F}$ that captures the behavior of the algorithm on a fixed input as a function of its random bits. In the case of space-bounded algorithms, we can take $\mathcal{F}$ to be the class of functions computable by polynomial-width standard-order read-once branching programs (ROBPs), defined below.

Definition 1.2 (ROBPs).

Let $w,n\in\mathbb{N}$ . A width- $w$ length- $n$ standard-order ROBP¹¹1The qualifier “standard-order” is often omitted; it emphasizes the fact that the program reads the input bits from left to right. is a directed graph in which the vertices are arranged in layers $V_{0},V_{1},\dots,V_{n}$ satisfying $|V_{i}|\leq w$ for every $i$ . For every $i\in\{0,1,\dots,n-1\}$ and every $v\in V_{i}$ , there are two outgoing edges leading from $v$ to $V_{i+1}$ , labeled $0$ and $1$ (the “ $0$ -edge” and the “ $1$ -edge” respectively). There is a designated “start vertex” $v_{0}\in V_{0}$ . Each input $x\in\{0,1\}^{n}$ defines a walk through the program: we start at $v_{0}$ , and in step $i\in[n]$ , we traverse the outgoing $x_{i}$ -edge of our current vertex. In this manner, we arrive at a final vertex $v_{n}\in V_{n}$ . Each vertex in $V_{n}$ is labeled either “accept” or “reject,” and the program accepts or rejects $x$ based on the label of $v_{n}$ . In this way, the program defines a function $f\colon\{0,1\}^{n}\to\{0,1\}$ .

For each fixed input, the output of a space- $S$ algorithm can be computed by a width- $w$ length- $n$ standard-order ROBP that reads the $n$ random bits used by the algorithm, where $w$ and $n$ are both bounded by $2^{O(S)}$ . Consequently, if we could design an explicit²²2I.e., the space complexity of the generator should be proportional to its seed length. PRG for width- $w$ length- $n$ standard-order ROBPs with the optimal seed length $O(\log(wn/\varepsilon))$ , then we could derandomize $\mathsf{BPL}$ by deterministically simulating the randomized algorithm on all possible outputs of the generator.

Decades ago, Nisan designed an explicit PRG for width- $w$ length- $n$ standard-order ROBPs with non-optimal seed length $O(\log(wn/\varepsilon)\cdot\log n)$ [28]. To this day, Nisan’s PRG is the best PRG known for polynomial-width standard-order ROBPs.

1.1 Regular and Permutation Branching Programs

Because it has turned out to be extremely difficult to design better PRGs for polynomial-width standard-order ROBPs, researchers have investigated ROBPs with additional structural restrictions. Two of the most well-studied classes are regular ROBPs and permutation ROBPs, defined next.

Definition 1.3 (Regular and permutation ROBPs).

An ROBP with layers $V_{0},V_{1},\dots,V_{n}$ is regular if every vertex $v\in V_{1}\cup\dots\cup V_{n}$ has precisely two incoming edges. If these two incoming edges have distinct labels ( $0$ and $1$ ) for each $v$ , then we say that the program is a permutation ROBP.

Braverman, Rao, Raz, and Yehudayoff showed that there is an explicit PRG that $\varepsilon$ -fools width- $w$ length- $n$ standard-order regular ROBPs with seed length $\widetilde{O}(\log(w/\varepsilon)\cdot\log n)$ [5]. This beats Nisan’s seed length [28] provided that $w\ll n$ and $\varepsilon\gg 1/n$ . Their PRG construction consists of an appropriately-parameterized version of the so-called Impagliazzo-Nisan-Wigderson (INW) generator [21]. For constant-width standard-order permutation ROBPs, the seed length can be improved to $O(\log n\cdot\log(1/\varepsilon))$ [6, 22, 13, 33]. However, we emphasize that when $\varepsilon=1/n$ , there are still no known explicit PRGs with seed length $o(\log^{2}n)$ , even for the case of constant-width standard-order permutation ROBPs.

1.2 Width- $2$ , Width- $3$ , and Width- $4$ Branching Programs

There has also been some success at beating Nisan’s PRG in the case of extremely narrow ROBPs, with no structural restrictions. In the 1990s, Saks and Zuckerman showed that any “small-bias distribution” [27] fools width- $2$ branching programs, and consequently, there is an explicit PRG that fools width- $2$ programs with the optimal seed length $O(\log(n/\varepsilon))$ [32, 2, 16, 23].

Width- $3$ programs turned out to be much more challenging. Nevertheless, Meka, Reingold, and Tal managed to construct an explicit PRG for width- $3$ standard-order ROBPs with seed length $\widetilde{O}(\log n\cdot\log(1/\varepsilon))$ [25]. Meka, Reingold, and Tal’s PRG [25] follows the “iterated restrictions with early termination” paradigm. First, they show how to assign pseudorandom values to a pseudorandom subset of a width- $3$ ROBP’s input variables in such a way that the expectation of the program is approximately preserved. Second, they show that after several such rounds of pseudorandom restrictions, the program simplifies with high probability, in the sense that it “almost” becomes a permutation ROBP. Finally, they show that the INW generator fools this “near-permutation program” with a good seed length.

For width- $4$ standard-order ROBPs, no explicit PRGs are known with seed length $o(\log^{2}n)$ . The width- $4$ case brings new challenges that are not present in the width- $2$ and width- $3$ cases. For example, width- $4$ ROBPs can compute read-once “ $\mathsf{AND}\circ\mathsf{OR}\circ\mathsf{PARITY}$ ” formulas, which have been highlighted as a challenging case for the “iterated restrictions with early termination” paradigm [17]. These formulas are provably not “simple” enough to be fooled by the INW generator with seed length $o(\log^{2}n)$ [6, 19], and they apparently do not get any “simpler” under restrictions, due to the layer of parity gates at the bottom. That being said, one can use small-bias distributions to $\varepsilon$ -fool read-once $\mathsf{AND}\circ\mathsf{OR}\circ\mathsf{PARITY}$ formulas with a seed length of $O(\log n\cdot\log(1/\varepsilon))$ .³³3After applying the parity gates, the resulting distribution still has small bias, and every $\delta$ -biased distribution fools read-once CNFs with error $\exp(-\Omega(\log(1/\delta)/\log n))$ [7, 14]. This perhaps suggests that we can be optimistic about fooling all width- $4$ ROBPs with a similar seed length.

1.3 Hitting Set Generators

Another approach for making progress on the $\mathsf{L}$ vs. $\mathsf{BPL}$ problem is to look at relaxations of the PRG concept. The most famous such relaxation is the classic hitting set generator (HSG) concept, defined next.

Definition 1.4 (HSGs).

Let $\mathcal{F}$ be a class of functions $f\colon\{0,1\}^{n}\to\{0,1\}$ and let $\varepsilon>0$ . An $\varepsilon$ -hitting set for $\mathcal{F}$ is a set $H\subseteq\{0,1\}^{n}$ such that for every $f\in\mathcal{F}$ , if $\operatorname*{\mathbb{E}}[f]>\varepsilon$ , then there is some $x\in H$ such that $f(x)=1$ . An $\varepsilon$ -HSG for $\mathcal{F}$ is a function $G\colon\{0,1\}^{s}\to\{0,1\}^{n}$ such that the image of $G$ is an $\varepsilon$ -hitting set for $\mathcal{F}$ .

Every $\varepsilon$ -PRG for a class $\mathcal{F}$ is also an $\varepsilon$ -HSG, but not vice versa. By working through the definitions, one can easily show that explicit HSGs for polynomial-width ROBPs with seed length $O(\log n)$ would imply $\mathsf{L}=\mathsf{RL}$ , where $\mathsf{RL}$ is the variant of $\mathsf{BPL}$ in which we only allow algorithms with one-sided error. In fact, it turns out that such HSGs would imply $\mathsf{L}=\mathsf{BPL}$ [11, 29]. Constructing HSGs is thus a route to proving $\mathsf{L}=\mathsf{BPL}$ that is potentially easier than constructing PRGs. However, despite the extra flexibility of the HSG definition, we would like to highlight the fact that there are currently no known explicit HSGs for width- $4$ standard-order ROBPs with seed length $o(\log^{2}n)$ .

1.4 Our Contributions

In this work, we establish new connections between the problems discussed above. Our main result says that if we could construct improved explicit PRGs for constant-width standard-order permutation ROBPs in the low-error regime, then we would get improved explicit HSGs for width- $4$ standard-order ROBPs.

Theorem 1.5 (PRGs for width- $6$ permutation programs $\implies$ HSGs for width- $4$ programs).

Let $c\in[1,2)$ be any constant. Assume that for every $n\in\mathbb{N}$ , there exists an explicit $(1/n)$ -PRG for width- $6$ length- $n$ standard-order permutation ROBPs with seed length $\widetilde{O}(\log^{c}n)$ . Then for every $n\in\mathbb{N}$ and every $\varepsilon\in(0,1)$ , there exists an explicit $\varepsilon$ -HSG for width- $4$ length- $n$ standard-order ROBPs with seed length $\widetilde{O}(\log^{c}n+\log n\cdot\log(1/\varepsilon))$ .

For context, prior work has shown that improved PRGs for regular ROBPs of polynomial width would have huge implications [31, 3, 24]. Indeed, Lee, Pyne, and Vadhan showed that every function computable by a width- $w$ length- $n$ standard-order ROBP can also be computed by a standard-order regular ROBP of width $O(wn)$ [24]. Our new reduction shows that improved PRGs for standard-order permutation ROBPs of constant width (a much weaker model) would already have significant consequences.

Our reduction can be divided into two parts, each of which is interesting in its own right. First, we revisit Meka, Reingold, and Tal’s reduction from the problem of fooling width- $3$ ROBPs to the problem of fooling “near-permutation” programs [25]. We show a reduction to the problem of fooling programs that exactly satisfy the permutation condition, albeit of width $6$ instead of $3$ :

Theorem 1.6 (Fooling width- $6$ permutation programs $\implies$ fooling width- $3$ programs).

There exists a constant $C>0$ such that the following holds. Assume that for every $n\in\mathbb{N}$ and $\delta\in(0,1)$ , there exists an explicit $\delta$ -PRG for width- $6$ length- $n$ standard-order permutation ROBPs with seed length $s(n,\delta)$ . Then, for every $n\in\mathbb{N}$ and $\varepsilon\in(0,\frac{1}{\log\log n})$ , there exists an explicit $\varepsilon$ -PRG for width- $3$ length- $n$ standard-order ROBPs with seed length $s(n,\delta)+\widetilde{O}(\log(n/\varepsilon))$ , where $\delta=\varepsilon^{C\cdot\log\log(n/\varepsilon)}$ .

Given Theorem 1.6, we can recover Meka, Reingold, and Tal’s $\widetilde{O}(\log n\cdot\log(1/\varepsilon))$ seed length for fooling width- $3$ standard-order ROBPs [25] (up to log log factors) by plugging in the state-of-the-art seed length $s(n,\delta)=O(\log n\cdot\log(1/\delta))$ for fooling constant-width standard-order permutation ROBPs [22, 13, 33]. More importantly, Theorem 1.6 shows that hypothetical improved PRGs for constant-width permutation ROBPs would translate to improved PRGs for width- $3$ ROBPs.

Second, we show how to convert low-error PRGs for width- $w$ ROBPs into HSGs for width- $(w+1)$ ROBPs, for any $w$ :

Theorem 1.7 (PRGs for width- $w$ programs $\implies$ HSGs for width- $(w+1)$ programs).

Let $\alpha>0$ be a constant such that $e^{\alpha-1}+\alpha<1/2$ ,⁴⁴4This is satisfied when $\alpha<\alpha_{*}\approx 0.095.$ and let $w\in\mathbb{N}$ be any constant. Assume that for every $n\in\mathbb{N}$ , there exists an explicit PRG for width- $w$ standard-order ROBPs with error $\alpha/n$ and seed length $s(n)$ . Then for every $n\in\mathbb{N}$ and every $\varepsilon>0$ , there exists an explicit $\varepsilon$ -HSG for width- $(w+1)$ standard-order ROBPs with seed length $O(s(n)+\log n\cdot\log(1/\varepsilon))$ .

Conceivably, one could hope to strengthen Theorem 1.7 to the point that it could be iterated. By induction on width, such a strengthened version could imply explicit HSGs for all constant-width standard-order ROBPs with seed length $o(\log^{2}n)$ . We find this idea exciting, even if it is admittedly quite speculative.

Our main result (Theorem 1.5) readily follows from Theorems 1.6 and 1.7, as we now briefly explain.

Proof of Theorem 1.5, given Theorems 1.6 and 1.7.

If we truncate a $\delta$ -PRG for width- $6$ standard-order permutation ROBPs, then we get another $\delta$ -PRG for width- $6$ standard-order permutation ROBPs (of shorter length). Therefore, the assumption of Theorem 1.5 implies the assumption of Theorem 1.6 with $s(n,\delta)=\widetilde{O}(\log^{c}(n/\delta))$ . Therefore, by Theorem 1.6, for every $n\in\mathbb{N}$ , there exists an explicit PRG that fools width- $3$ standard-order ROBPs with error $0.01/n$ and seed length $s^{\prime}(n)=\widetilde{O}(\log^{c}(n/\delta))$ , where $\delta=(0.01/n)^{C\cdot\log\log(n^{2}/0.01)}$ . Simplifying, we have $s^{\prime}(n)=\widetilde{O}(\log^{c}n)$ . Applying Theorem 1.7 completes the proof. $\hfill\blacktriangleleft$

1.5 Context: Weighted Pseudorandom Generators

Theorems 1.5, 1.6, and 1.7 are especially interesting in light of a recent line of work on weighted pseudorandom generators (WPRGs), defined next.

Definition 1.8 (WPRGs).

Let $\mathcal{F}$ be a class of functions $f\colon\{0,1\}^{n}\to\mathbb{R}$ and let $\varepsilon>0$ . An $\varepsilon$ -WPRG for $\mathcal{F}$ is a pair $(G,\rho)$ , where $G\colon\{0,1\}^{s}\to\{0,1\}^{n}$ and $\rho\colon\{0,1\}^{s}\to\mathbb{R}$ , such that for every $f\in\mathcal{F}$ , we have

\left|\operatorname*{\mathbb{E}}[f]-\operatorname*{\mathbb{E}}_{x\sim U_{s}}[f% (G(x))\cdot\rho(x)]\right|\leq\varepsilon.

Weighted PRGs were introduced by Braverman, Cohen, and Garg [4]. The key innovation in Definition 1.8 is that the weights $\rho(x)$ can be negative. One can show that WPRGs are “intermediate” between PRGs and HSGs.

The WPRG paradigm has turned out to be especially helpful in low-error regimes. For example, recent work has shown how to construct explicit WPRGs that fool the following models with error $1/n$ and seed length $\widetilde{O}(\log^{3/2}n)$ :

$\blacksquare$

Constant-width standard-order regular ROBPs [10, 8, 9, 12].
$\blacksquare$

Width- $3$ standard-order ROBPs [10, 8].
$\blacksquare$

“Unbounded-width” standard-order permutation ROBPs [30, 10, 8, 12].

In contrast, in all three of the cases listed above, there are no known explicit unweighted PRGs with error $1/n$ and seed length $o(\log^{2}n)$ .⁵⁵5In fact, in the case of unbounded-width standard-order permutation ROBPs, unweighted PRGs with error $1/n$ and seed length $o(\log^{2}n)$ provably do not exist [18].

Unfortunately, our new reductions (Theorems 1.5, 1.6, and 1.7) require unweighted PRGs. If our reductions could be adapted to work with negative weights, then we would get an explicit HSG for width- $4$ standard-order ROBPs with seed length $\widetilde{O}(\log^{3/2}n+\log n\cdot\log(1/\varepsilon))$ .

1.6 Techniques

Our reductions can be broken down into several smaller parts; see Figure 1. One common theme in our proofs is that, following prior work [15, 3, 26], we study modified versions of the ROBP model in which it is possible to accept or reject “early,” before reaching the end of the computation. We find it most convenient to work with the following models.

Figure 1: The reductions in this paper. Many of the reductions are slightly stronger than what the diagram suggests. For example, rather than a low-error PRG, Lemma 4.3 actually requires merely a low-threshold HSG for width-

w

ROBPs. Explicit constructions of such generators are known unconditionally in the

w=3

case [15]. On the other hand, we highlight the fact that Corollary 4.2 requires an unweighted PRG with low error. If we could eliminate either one of these requirements, then we could construct explicit HSGs for width-

4

ROBPs with seed length

o(\log^{2}n)

.

Definition 1.9 ( $\wedge$ -programs and $\vee$ -programs).

An $\wedge$ -program is a standard-order ROBP in which every edge is labeled as either “accepting” or “rejecting” (in addition to the usual binary edge label). Given an input $x$ , if every edge that the ROBP traverses is an accepting edge, then we say that the $\wedge$ -program accepts $x$ ; otherwise, we say that the $\wedge$ -program rejects $x$ . An $\vee$ -program is defined similarly, except that an $\vee$ -program accepts if it traverses at least one accepting edge and it rejects otherwise.

An $\wedge$ -program or an $\vee$ -program of width $w$ can trivially be simulated by a standard-order ROBP of width $w+1$ , but note that (a) the difference between width $w$ and width $w+1$ is crucial in this work, and (b) we are concerned with structural properties such as the permutation condition that are not preserved by such a trivial simulation.

1.6.1 Near-Permutation Programs vs. Exact Permutation Programs

As discussed previously, Meka, Reingold, and Tal reduced the problem of fooling width- $3$ ROBPs to the problem of fooling “near-permutation” programs [25]. In more detail, by “near-permutation” programs, we refer to programs that are approximated in a certain sense by programs with few colliding layers. (A “colliding layer” is a layer that violates the definition of a permutation ROBP.) Later, Chen, Hoza, Lyu, Tal, and Wu improved the number of colliding layers in this reduction [10].

For the proof of Theorem 1.6, our main observation is that any width- $w$ program with $t$ colliding layers can be written as a sum of $w^{t}$ many width- $w$ permutation $\wedge$ -programs. We prove this by a simple “guess and check” argument; see Lemma 3.3 for details.

The permutation $\wedge$ -program model is stronger than the standard-order permutation ROBP model, but previous work by Bogdanov, Hoza, Prakriya, and Pyne implies that to fool width- $w$ permutation $\wedge$ -programs, it suffices to fool width- $(2w)$ standard-order permutation ROBPs [3]. Thus, combining their work with our observation, we see that PRGs for width- $6$ standard-order permutation ROBPs automatically fool width- $3$ programs that have a few colliding layers.

The proof of Theorem 1.6 requires some additional technical details, mainly to handle approximation errors that arise in Meka, Reingold, and Tal’s framework [25]. See Section 3 for details.

1.6.2 Using a PRG for Width $𝒘$ to Design an HSG for Width $w+1$

Let $X$ be a distribution that fools width- $w$ ROBPs with error $0.01/n$ . The first step in the proof of Theorem 1.7 is to prove that $\operatorname{Supp}(X)$ is a $0.4$ -hitting set for width- $w$ $\wedge$ -programs.

To explain the intuition, let us consider a special case of width- $w$ $\wedge$ -programs, namely, a function of the form $f(x)=f_{1}(x)\wedge\dots\wedge f_{t}(x)$ , where $f_{1},\dots,f_{t}$ are width- $w$ standard-order ROBPs on disjoint variables. Since we are aiming to construct a $0.4$ -hitting set, let us assume that $\operatorname*{\mathbb{E}}[f]>0.4$ . Letting $\delta_{i}=1-\operatorname*{\mathbb{E}}[f_{i}]$ , we have

\operatorname*{\mathbb{E}}[f]=\prod_{i=1}^{t}(1-\delta_{i})\leq\prod_{i=1}^{t}% e^{-\delta_{i}}=e^{-\sum_{i=1}^{t}\delta_{i}},

so $\sum_{i=1}^{t}\delta_{i}\leq\ln(1/\operatorname*{\mathbb{E}}[f])<0.92$ . Therefore,

$\displaystyle\Pr[f(X)=0]=\Pr[f_{1}(X)=0\vee\dots\vee f_{t}(X)=0]$	$\displaystyle\leq\sum_{i=1}^{t}\Pr[f_{i}(X)=0]$	(Union bound)
	$\displaystyle\leq\sum_{i=1}^{t}(\delta_{i}+0.01/n)$
	$\displaystyle\leq 0.01+\sum_{i=1}^{t}\delta_{i}$
	$\displaystyle<0.93.$

Thus, indeed, $\operatorname{Supp}(X)$ hits $f$ .⁶⁶6Note that this argument breaks down if we try to replace $X$ with a WPRG, because the union bound no longer holds.

Now suppose more generally that $f$ is a width- $w$ $\wedge$ -program. In this case, we let $\delta_{i}$ be the probability that $f$ traverses a rejecting edge in step $i$ . By a probabilistic construction (Lemma 4.1), we show that $f$ can be modified to ensure that $\sum_{i=1}^{n}\delta_{i}\leq\ln(1/\operatorname*{\mathbb{E}}[f])$ . Consequently, $\operatorname{Supp}(X)$ is a $0.4$ -hitting set for width- $w$ $\wedge$ -programs by a similar “union bound” calculation as above. The probabilistic modification of $f$ is arguably the most novel component of our reductions.

For the next step in the proof of Theorem 1.7, we build on Gopalan, Meka, Reingold, Trevisan, and Vadhan’s techniques [15]. In our terminology, they show how to convert an explicit $(\frac{\varepsilon^{2}}{2n})$ -HSG for width- $w$ $\wedge$ -programs into an explicit $\varepsilon$ -HSG for width- $(w+1)$ standard-order ROBPs [15, Theorem 6.5]. They used this reduction to construct a near-optimal HSG for width- $3$ standard-order ROBPs. We cannot apply their reduction directly, because it requires a low-threshold HSG and we merely have a $0.4$ -HSG. Therefore, we extend their reduction. We show that an explicit $\varepsilon_{\wedge}$ -HSG for width- $w$ $\wedge$ -programs can be combined with an explicit $\varepsilon_{\vee}$ -HSG for width- $w$ $\vee$ -programs to produce an explicit $(\varepsilon_{\wedge}+\varepsilon_{\vee})$ -HSG for width- $(w+1)$ standard-order ROBPs (Lemma 4.5). One can easily show that $\operatorname{Supp}(X)$ is a $0.01$ -hitting set for width- $w$ $\vee$ -programs (Lemma 4.3), so we get a $0.41$ -HSG for width- $(w+1)$ standard-order ROBPs.

Finally, we use an adaptation of Hoza and Zuckerman’s error reduction technique [20] to construct an $\varepsilon$ -HSG for width- $(w+1)$ standard-order ROBPs for any $\varepsilon$ . This error reduction step blows up the seed length by a factor of $O(\log(1/\varepsilon))$ , but we can get a final seed length of $O(s+\log n\cdot\log(1/\varepsilon))$ instead of $O(s\cdot\log(1/\varepsilon))$ by using the standard “sampler trick.” See Section 4 for details.

1.7 Organization

After some preliminaries in Section 2, we prove Theorem 1.6 in Section 3, and then we prove Theorem 1.7 in Section 4.

2 Preliminaries

2.1 Subprograms, Substrings, Hitting Sets, and Restrictions

Let $f$ be an ROBP with layers $V_{0},V_{1},\dots,V_{n}$ . For each $i\in\{0,1,\dots,n\}$ and each $u\in V_{i}$ , we define the “subprogram” $f_{u\to}$ to be a version of $f$ in which $u$ is effectively the new start vertex. More precisely, $f_{u\to}$ is a length- $n$ program on the layers $V_{0}^{\prime},V_{1}^{\prime},\dots,V_{i}^{\prime},V_{i+1},\dots,V_{n}$ , where $|V_{0}^{\prime}|=\dots=|V_{i}^{\prime}|=1$ . All transitions in the first $i$ steps lead to $u$ , and after that, the program is identical to $f$ . We furthermore define $p_{u\to}=\operatorname*{\mathbb{E}}[f_{u\to}]$ .

If $x\in\{0,1\}^{n}$ and $1\leq i\leq j\leq n$ , we use the notation $x_{i\dots j}$ to denote the string $x_{i}x_{i+1}\dots x_{j}$ .

Let $f\colon\{0,1\}^{n}\to\{0,1\}$ and $H\subseteq\{0,1\}^{n}$ . We say that $H$ “hits” $f$ if there is some $x\in H$ such that $f(x)=1$ .

A restriction is a string $\rho\in\{0,1,\star\}^{n}$ . If $f\colon\{0,1\}^{n}$ and $\rho\in\{0,1,\star\}^{n}$ , then we define the restricted function $f|_{\rho}\colon\{0,1\}^{n}\to\{0,1\}$ by the rule $f|_{\rho}(x)=f(x^{\prime})$ , where, for every $i\in[n]$ ,

x^{\prime}_{i}=\begin{cases}\rho_{i}&\text{if }\rho_{i}\neq\star\\ x_{i}&\text{if }\rho_{i}=\star.\end{cases}

2.2 Probability

We rely on the following standard lemma from the theory of PRGs.

Lemma 2.1 (Sandwiching lemma).

Let $f_{-},f,f_{+}\colon\{0,1\}^{n}\to\mathbb{R}$ and let $X$ be a distribution over $\{0,1\}^{n}$ . Assume that $f_{-}(x)\leq f(x)\leq f_{+}(x)$ for every $x$ ; assume that $\operatorname*{\mathbb{E}}[f_{+}-f_{-}]\leq\varepsilon$ ; and assume that $X$ fools $f_{-}$ and $f_{+}$ with error $\delta$ . Then $X$ fools $f$ with error $\varepsilon+\delta$ .

Proof.

\operatorname*{\mathbb{E}}[f(X)]\leq\operatorname*{\mathbb{E}}[f_{+}(X)]\leq% \operatorname*{\mathbb{E}}[f_{+}]+\delta\leq\operatorname*{\mathbb{E}}[f]+% \varepsilon+\delta,

and

\operatorname*{\mathbb{E}}[f(X)]\geq\operatorname*{\mathbb{E}}[f_{-}(X)]\geq% \operatorname*{\mathbb{E}}[f_{-}]-\delta\geq\operatorname*{\mathbb{E}}[f]-% \varepsilon-\delta.\

$\hfill\blacktriangleleft$

We also rely on the following elementary inequality.

Lemma 2.2 (Reverse union bound).

Let $E_{1},E_{2},\dots,E_{n}$ be events, and let $p=\Pr[E_{1}\wedge\dots\wedge E_{n}]$ . Then

\sum_{i=1}^{n}\Pr[\neg E_{i}\mid E_{1},E_{2},\dots,E_{i-1}]\leq\ln(1/p).

Proof.

Let $\delta_{i}=\Pr[\neg E_{i}\mid E_{1},E_{2},\dots,E_{i-1}]$ . Then

\displaystyle p

\displaystyle=\prod_{i=1}^{n}(1-\delta_{i})\leq\prod_{i=1}^{n}\exp(-\delta_{i}% )=\exp\left(-\sum_{i=1}^{n}\delta_{i}\right),

and hence $\sum_{i=1}^{n}\delta_{i}\leq\ln(1/p)$ . $\hfill\blacktriangleleft$

3 Conditional Low-Error PRGs for Width- $3$ ROBPs

3.1 Fooling Programs That Have a Few Colliding Layers

The first step in the proof of Theorem 1.6 is the following lemma from the work of Bogdanov, Hoza, Prakriya, and Pyne [3, Lemma 20].

Lemma 3.1 (Fooling permutation $\wedge$ -programs [3]).

Let $X$ be a distribution over $\{0,1\}^{n}$ . If $X$ fools width- $(2w)$ standard-order permutation ROBPs with error $\varepsilon$ , then $X$ fools width- $w$ permutation $\wedge$ -programs with error $2\varepsilon$ .

Technically, the model that Bogdanov, Hoza, Prakriya, and Pyne study (“unanimity programs”) [3] is slightly weaker than our $\wedge$ -program model, because they require the two outgoing edges of each vertex to be either both accepting or both rejecting. However, their proof applies equally well to both models.

Combining the assumption of Theorem 1.6 with Lemma 3.1 gives us a PRG for width- $3$ standard-order permutation $\wedge$ -programs. The next step is to show that we can fool width- $3$ standard-order $\wedge$ -programs that have a few colliding layers, defined next.

Definition 3.2 (Colliding layer).

Let $f$ be an ROBP with layers $V_{0},\dots,V_{n}$ . We say that layer $i$ is colliding, where $i\in\{0,1,\dots,n-1\}$ , if there exist two edges going from $V_{i}$ to $V_{i+1}$ with the same binary label leading to the same vertex.

Lemma 3.3 (Fooling $\wedge$ -programs with a few colliding layers).

Let $f$ be a width- $w$ length- $n$ $\wedge$ -program with at most $t$ colliding layers. Then $f$ can be written as a sum of $w^{t}$ many width- $w$ permutation $\wedge$ -programs.

Proof.

Let the layers of $f$ be $V_{0},\dots,V_{n}$ . Let $\{i_{1},i_{2},\dots,i_{t}\}$ be the set of colliding layers. For every $\vec{v}=(v_{i_{1}},\dots,v_{i_{t}})\in V_{i_{1}}\times V_{i_{2}}\times\dots% \times V_{i_{t}}$ , we will modify $f$ to construct a width- $w$ standard-order permutation $\wedge$ -program $f_{\vec{v}}$ . The construction is as follows.

1.

Let $R=(V_{i_{1}}\setminus\{v_{i_{1}}\})\cup\dots\cup(V_{i_{t}}\setminus\{v_{i_{t}}\})$ .
2.

Redirect the outgoing edges of vertices in $R$ in such a way that there are no remaining collisions, and re-label them as “rejecting” edges.

Observe that $f_{\vec{v}}(x)=1$ if and only if $f(x)$ visits the vertices $v_{i_{1}},\dots,v_{i_{t}}$ and accepts. Consequently, $f=\sum_{\vec{v}}f_{\vec{v}}$ . $\hfill\blacktriangleleft$

Next, we show how to fool width- $3$ standard-order ROBPs that are well-approximated by a suffix with few colliding layers. More precisely, we will fool $(3,t,\varepsilon)$ -programs, defined below.

Definition 3.4 ( $(w,t,\varepsilon)$ -program).

Let $f$ be a length- $n$ standard-order ROBP with layers $V_{0},V_{1},\dots,V_{n}$ . We say that $f$ is a $(w,t,\varepsilon)$ -program if $f$ has width at most $w$ and there exists an $i\in\{0,1,\dots,n\}$ such that:

1.

There are at most $t$ colliding layers among layers $i,i+1,\dots,n-1$ .
2.

If we sample $x\sim U_{n}$ , then

$\Pr_{x}[\exists u,v\in V_{i}\text{ such that }f_{u\to}(x)\neq f_{v\to}(x)]\leq\varepsilon.$

Lemma 3.5 (Fooling $\wedge$ -programs with $t$ colliding layers $\implies$ fooling $(w,t,\varepsilon)$ -programs).

Let $X$ be a distribution over $\{0,1\}^{n}$ and let $w\geq 3$ . If $X$ fools width- $\binom{w}{2}$ $\wedge$ -programs that have at most $t$ colliding layers with error $\delta$ , then $X$ fools $(w,t,\varepsilon)$ -programs with error $2w\cdot(\varepsilon+\delta)$ .

Proof.

Let $f$ be a $(w,t,\varepsilon)$ -program, and let $i$ be as in Definition 3.4. Let $u_{*}$ be any element of $V_{i}$ . For each $v\in V_{i}\setminus\{u_{*}\}$ , define

h_{v}(x)=f_{u_{*}\to}(x)\oplus f_{v\to}(x).

We will use the following two approximators to sandwich $f$ :

	$\displaystyle f_{+}$	$\displaystyle=f_{u_{}\to}+\sum_{v\in V_{i}\setminus\{u_{}\}}h_{v}$
	$\displaystyle f_{-}$	$\displaystyle=f_{u_{}\to}-\sum_{v\in V_{i}\setminus\{u_{}\}}h_{v},$

where the summation is over $\mathbb{R}$ . For every $x\in\{0,1\}^{n}$ , we have

f_{-}(x)\leq f(x)\leq f_{+}(x).

To see this, note that $f$ on $x$ either reaches $u_{*}$ , or else it reaches some $v\neq u_{*}$ , and then we can consider the $h_{v}$ term. Furthermore,

\operatorname*{\mathbb{E}}[f_{+}-f_{-}]=2\sum_{v\in V_{i}\setminus\{u_{*}\}}% \operatorname*{\mathbb{E}}[h_{v}]\leq 2w\varepsilon.

Thus, indeed, $f$ is sandwiched between $f_{-}$ and $f_{+}$ with error $2w\varepsilon$ .

Now we will prove that $X$ fools $f_{-}$ and $f_{+}$ . The program $f_{u_{*}\to}$ can be computed by a width- $w$ standard-order ROBP with at most $t$ colliding layers. The model of width- $\binom{w}{2}$ $\wedge$ -programs with at most $t$ colliding layers is only more general, so $X$ fools $f_{u_{*}\to}$ with error $\delta$ . Now fix $v\in V_{i}\setminus\{u_{*}\}$ ; we will show that $X$ fools $h_{v}$ .

We can construct an $\wedge$ -program $g$ that computes $h_{v}$ as follows.

$\blacksquare$

Each vertex of $g$ represents an unordered pair of vertices $\{u^{\prime},v^{\prime}\}$ in the corresponding layer of $f$ .
$\blacksquare$

Let $b\in\{0,1\}$ and let $u^{\prime\prime},v^{\prime\prime}$ be the vertices reached from $u^{\prime},v^{\prime}$ by following the outgoing $b$ -edge. If $u^{\prime\prime}\neq v^{\prime\prime}$ , then the outgoing $b$ -edge of $\{u^{\prime},v^{\prime}\}$ leads to $\{u^{\prime\prime},v^{\prime\prime}\}$ and is an accepting edge. If $u^{\prime\prime}=v^{\prime\prime}$ , then the outgoing $b$ -edge of $\{u^{\prime},v^{\prime}\}$ can lead to an arbitrary vertex and is a rejecting edge.

Observe that $g$ has width $\binom{w}{2}$ . Furthermore, every colliding layer of $g$ is also a colliding layer of $f$ . Therefore, $g$ has at most $t$ colliding layers. Consequently, $X$ fools $h_{v}$ with error $\delta$ . Therefore, $X$ fools $f_{+}$ and $f_{-}$ with error $w\delta$ . Applying Lemma 2.1 completes the proof. $\hfill\blacktriangleleft$

3.2 Reducing the Number of Colliding Layers in a Width- $3$ Program

To complete the proof of Theorem 1.6, we will take Meka, Reingold, and Tal’s approach [25]: we will apply a few pseudorandom restrictions, and we will argue that with high probability, the restricted program is “almost” a permutation program. In particular:

Lemma 3.6 (Restrictions for width- $3$ programs [25, 10]).

For every $n\in\mathbb{N}$ and $\varepsilon>0$ , there exists an explicit restriction generator $\mathcal{R}\colon\{0,1\}^{s}\to\{0,1,\star\}^{n}$ , with $s=\widetilde{O}(\log(n/\varepsilon))$ , such that if $f$ is a width- $3$ standard-order ROBP and we sample $\rho\sim\mathcal{R}(U_{s})$ :

1.

The restriction $\rho$ preserves the expectation of $f$ up to error $\varepsilon$ . That is,

$\left|\operatorname*{\mathbb{E}}_{\rho,U}[f|_{\rho}(U)]-\operatorname*{\mathbb% {E}}[f]\right|\leq\varepsilon,$

where $U$ is a uniform random string that is independent of $\rho$ .
2.

With probability $1-\varepsilon$ over $\rho$ , the restricted function $f|_{\rho}$ can be computed by a $(3,t,\varepsilon)$ -program where $t=O((\log(1/\varepsilon)+\log\log\log n)\cdot\log\log(n/\varepsilon))$ .

(See Section 2 for the definition of $f|_{\rho}$ .) In Meka, Reingold, and Tal’s original analysis [25], the number of colliding layers ( $t$ ) is $\operatorname{poly}(1/\varepsilon)\cdot\log\log n$ (and they use a slightly different notion of approximation). Later, Chen, Hoza, Lyu, Tal, and Wu refined their analysis [10]. Their bound on the number of colliding layers was roughly $\log^{5}(1/\varepsilon)$ , but it turns out that merely fiddling with some parameters in their analysis is enough to prove the superior $\widetilde{O}(\log(1/\varepsilon)\cdot\log\log n)$ bound stated in Lemma 3.6. We explain some details below.

Proof sketch of Lemma 3.6.

We assume that the reader is familiar with Chen, Hoza, Lyu, Tal, and Wu’s analysis [10], and we merely explain what changes to make to their proofs.

$\blacksquare$

In their “Claim 7.25,” we should not assume $C$ is a constant. Their proof works for any $C$ , provided we choose a suitable value $p=1/\operatorname{poly}(C)$ .
$\blacksquare$

In their “Claim 7.30,” we should choose $C=16\ln^{1/4}(1/\delta)$ rather than $C=32$ . After making this change, there is no longer any need to assume $\ell\geq\log\ln(1/\delta)$ ; the claim holds provided $\ell\geq 4$ .
$\blacksquare$

In their “Lemma 7.31,” we should not assume $p$ is a constant. The lemma holds for any $p$ that is a power of $1/2$ , with a seed length of

$s=\widetilde{O}(w\cdot\log(n/\delta)\cdot\log(1/p)).$
$\blacksquare$

In their “Claim 7.35,” instead of taking $p$ to be a small enough constant, we should pick $p=1/\operatorname{polylog}(1/\delta)$ . In the proof, we should pick $C=16\ln^{1/4}(1/\delta)$ . We should define $\ell_{j}=\max\{4,\ell_{j-1}/2\}$ instead of $\ell_{j}=\ell_{j-1}/2$ . That way, at the end, we reach $\ell=4$ , $m=C^{\ell}=O(\log(1/\delta))$ , and $r=O(\log(1/\delta)\cdot\log\log(n/\delta))$ . Applying this modified version of Claim 7.35 with $\delta=\min\{\varepsilon^{4},1/(\log\log n)^{5}\}$ completes the proof of Lemma 3.6.

$\hfill\blacktriangleleft$

Proof of Theorem 1.6.

Let $G$ be the assumed $\delta$ -PRG. Our new PRG samples a restriction $\rho$ using Lemma 3.6 with error $\varepsilon/16$ , then samples a pseudorandom string $X$ from $G$ , and finally uses $X$ to fill in the stars of $\rho$ . The seed length is clearly $s(n,\delta)+\widetilde{O}(\log(n/\varepsilon))$ .

To prove that this works, let $f$ be a width- $3$ length- $n$ standard-order ROBP. By Lemma 3.6, $\rho$ preserves the expectation of $f$ to within $\varepsilon/16$ . Furthermore, except with probability $\varepsilon/16$ , the restricted function $f|_{\rho}$ can be computed by a $(3,t,\varepsilon/16)$ -program where $t=O((\log(1/\varepsilon)+\log\log\log n)\cdot\log\log(n/\varepsilon))$ . Since we have assumed that $\varepsilon<\frac{1}{\log\log n}$ , the bound simplifies to $t=O(\log(1/\varepsilon)\cdot\log\log(n/\varepsilon))$ .

By Lemmas 3.1, 3.3, and 3.5, the distribution $X$ fools width- $3$ standard-order permutation $\wedge$ -programs with error $2\delta$ ; it fools width- $3$ standard-order $\wedge$ -programs that have at most $t$ colliding layers with error $2\delta\cdot 3^{t}$ ; and it fools $(3,t,\varepsilon/16)$ -programs with error $6\cdot(2\delta\cdot 3^{t}+\varepsilon/16)$ . (Note that $\binom{3}{2}=3$ .)

Summing up, our PRG fools $f$ with error $\varepsilon/16+\varepsilon/16+6\cdot(2\delta\cdot 3^{t}+\varepsilon/16)=% \varepsilon/2+\delta\cdot 12\cdot 3^{t}$ . If we choose the constant $C$ in the definition of $\delta$ large enough, then $\delta\cdot 12\cdot 3^{t}\leq\varepsilon/2$ , completing the proof. $\hfill\blacktriangleleft$

4 Conditional HSGs for Width- $4$ ROBPs

4.1 Hitting Width- $𝒘$ $\wedge$ -Programs

As discussed in Section 1.6, the first step in the proof of Theorem 1.7 is to show that in a $\wedge$ -program $f$ , without loss of generality, the expected number of rejecting edges traversed under a uniform random input is at most $\ln(1/\operatorname*{\mathbb{E}}[f])$ . Constant factors are important here; see Figure 2. We prove it by using the probabilistic method to reroute the rejecting edges; the details follow.

Figure 2: In Lemma 4.1, we care about the base of the logarithm in the bound

\ln(1/\operatorname*{\mathbb{E}}[f])

; a bound of

\log_{2}(1/\operatorname*{\mathbb{E}}[f])

would not be good enough. The reason is that down the road, to perform error reduction, we will need a

(1/2-\Omega(1))

-HSG (see Lemma 4.7). To construct such an HSG, we will use the fact that the bound

\ln(1/\operatorname*{\mathbb{E}}[f])

in Lemma 4.1 is strictly less than one even when

\operatorname*{\mathbb{E}}[f]

is slightly less than

1/2

, since

e>2

.

Lemma 4.1 (Expected number of rejecting edges traversed in an $\wedge$ -program).

For every width- $w$ $\wedge$ -program $f$ , there exists another width- $w$ $\wedge$ -program $g$ with the following two properties.

1.

$g$ computes the same function as $f$ .
2.

When $g$ reads a uniform random input, the expected number of rejecting edges that are traversed is at most $\ln(1/\operatorname*{\mathbb{E}}[f])$ .

Proof.

Let $V_{0},V_{1},\dots,V_{n}$ be the layers of vertices of $f$ . For each string $x\in\{0,1\}^{\leq n}$ , let $f[x]$ be the vertex that $f$ reaches after reading $x$ . For each $i\in\{0,1,\dots,n\}$ , let $A_{i}$ be the set of $x\in\{0,1\}^{i}$ such that when $f$ reads $x$ , every edge it traverses is an accepting edge. Furthermore, abusing notation, let $A_{i}$ denote the uniform distribution over the set $A_{i}$ . We construct $g$ using the probabilistic method as follows.

1.

For each $i\in[n]$ independently, we sample a string $X^{*}_{i}\sim A_{i}$ .
2.

Let $g$ be $f$ , except that for every $i\in[n]$ , all rejecting edges from $V_{i-1}$ to $V_{i}$ are redirected to point to $f[X^{*}_{i}]$ .

Since we only redirected rejecting edges, $g$ computes the same function as $f$ .

We will prove by induction that for every $i\in\{0,1,\dots,n\}$ , we have $g[U_{i}]\sim f[A_{i}]$ , where $U_{i}$ denotes a uniform random $i$ -bit string that is independent of the randomness used to construct $g$ . When $i=0$ , this is trivial. Now, assuming it holds for $i$ , we can sample $g[U_{i+1}]$ by the following steps.

1.

Sample $X$ uniformly at random from $A_{i}$ (note that $f[X]\sim g[U_{i}]$ ).
2.

Sample $Y\in\{0,1\}$ uniformly at random.
3.

If $XY\notin A_{i+1}$ , sample $X^{*}_{i+1}\sim A_{i+1}$ and output $f[X^{*}_{i+1}]$ .
4.

If $XY\in A_{i+1}$ , output $f[XY]$ .

Conditioned on the event $XY\notin A_{i+1}$ , clearly $g[U_{i+1}]\sim f[A_{i+1}]$ . Meanwhile, conditioned on the event that $XY\in A_{i+1}$ , the string $X Y$ is in fact uniformly distributed over $A_{i+1}$ , and hence once again $g[U_{i+1}]\sim f[A_{i+1}]$ . This completes the inductive step.

Consequently, if we sample $Z\sim U_{n}$ , then the expected number of rejecting edges traversed by $g(Z)$ is

	$\displaystyle\sum_{i=1}^{n}\Pr[g(Z)\text{ traverses a rejecting edge in step }i]$	$\displaystyle=\sum_{i=1}^{n}\Pr[Z_{1\dots i}\notin A_{i}\mid Z_{1\dots i-1}\in A% _{i-1}]$
		$\displaystyle\leq\ln(1/\operatorname*{\mathbb{E}}[f])$

by Lemma 2.2. The best case is at least as good as the average case, so there is some fixing of $g$ such that the expected number of rejecting edges traversed by $g(Z)$ with respect to the randomness of $Z$ alone is at most $\ln(1/\operatorname*{\mathbb{E}}[f])$ . $\hfill\blacktriangleleft$

Corollary 4.2 (PRGs for width- $w$ ROBPs are HSGs for width- $w$ $\wedge$ -programs).

Let $w,n\in\mathbb{N}$ and $\beta\in(0,1)$ , and let $\varepsilon_{\wedge}=e^{\beta-1}$ . For every width- $w$ length- $n$ $\wedge$ -program $f$ with $\operatorname*{\mathbb{E}}[f]>\varepsilon_{\wedge}$ , there is a set $\mathcal{A}_{f}$ of width- $w$ standard-order ROBPs such that the following hold.

1.

$|\mathcal{A}_{f}|=n$ .
2.

If $X$ is a distribution over $\{0,1\}^{n}$ that $(\beta/n)$ -fools $\mathcal{A}_{f}$ , then $\operatorname{Supp}(X)$ hits $f$ .

In particular, if $X$ fools all width- $w$ length- $n$ standard-order ROBPs with error $\beta/n$ , then $\operatorname{Supp}(X)$ hits $f$ .

Proof.

Let $g$ be the program from Lemma 4.1. For each $i\in[n]$ , there is a width- $w$ standard-order ROBP $g_{i}$ such that $g_{i}(x)=1$ if and only if $g(x)$ traverses a rejecting edge in step $i$ . Let $\mathcal{A}_{f}=\{g_{1},g_{2},\dots,g_{n}\}$ . Then

	$\displaystyle\Pr[f(X)=0]=\Pr[g_{1}(X)=1\vee\dots\vee g_{n}(X)=1]\leq\sum_{i=1}% ^{n}\operatorname*{\mathbb{E}}[g_{i}(X)]$	$\displaystyle\leq\sum_{i=1}^{n}(\operatorname*{\mathbb{E}}[g_{i}]+\beta/n)$
		$\displaystyle\leq\ln(1/\operatorname*{\mathbb{E}}[f])+\beta$
		$\displaystyle<1.\$

$\hfill\blacktriangleleft$

4.2 Hitting Width- $𝒘$ $\vee$ -Programs

Lemma 4.3 (HSGs for width- $w$ ROBPs are also HSGs for width- $w$ $\vee$ -programs).

For every width- $w$ length- $n$ $\vee$ -program $f$ , there is a width- $w$ length- $n$ standard-order ROBP $g_{f}$ such that $g_{f}\leq f$ and $\operatorname*{\mathbb{E}}[g_{f}]\geq\operatorname*{\mathbb{E}}[f]/n$ . Consequently, for every $H\subseteq\{0,1\}^{n}$ and every $\varepsilon_{\vee}>0$ , if $H$ is an $(\varepsilon_{\vee}/n)$ -hitting set for width- $w$ length- $n$ standard-order ROBPs, then $H$ is also an $\varepsilon_{\vee}$ -hitting set for width- $w$ length- $n$ $\vee$ -programs.

Proof.

For each $i\in[n]$ , there is a width- $w$ standard-order ROBP $f_{i}$ such that $f_{i}(x)=1$ if and only if $f(x)$ traverses an accepting edge in step $i$ . If we sample $X\sim U_{n}$ , then

\operatorname*{\mathbb{E}}[f(X)]=\operatorname*{\mathbb{E}}[f_{1}(X)\vee f_{2}% (X)\vee\dots\vee f_{n}(X)]\leq\sum_{i=1}^{n}\operatorname*{\mathbb{E}}[f_{i}],

so there is some $i$ such that $\operatorname*{\mathbb{E}}[f_{i}]\geq\operatorname*{\mathbb{E}}[f]/n$ . We can let $g_{f}=f_{i}$ . $\hfill\blacktriangleleft$

4.3 Hitting Width- $(w+1)$ Programs

We define the following associative operation on hitting sets.

Definition 4.4 (The $\mathbin{\circledast}$ operation).

For any two sets $H,H^{\prime}\subseteq\{0,1\}^{n}$ , we define

H\mathbin{\circledast}H^{\prime}=\{x_{1}x_{2}\dots x_{i}y_{i+1}y_{i+2}\dots y_% {n}:x\in H,y\in H^{\prime},0\leq i\leq n\}.

Furthermore, we define

H^{\mathbin{\circledast}t}=\underbrace{H\mathbin{\circledast}H\mathbin{% \circledast}\dots\mathbin{\circledast}H}_{t\text{ copies}}.

Note that $|H^{\mathbin{\circledast}t}|\leq(n\cdot|H|)^{t}$ .

As discussed in Section 1.6, Gopalan, Meka, Reingold, Trevisan, and Vadhan showed how to convert an $(\frac{\varepsilon^{2}}{2n})$ -hitting set $H$ for width- $w$ $\wedge$ -programs into an $\varepsilon$ -hitting set $H^{\prime}$ for width- $(w+1)$ standard-order ROBPs [15]. In particular, they showed that one can take $H^{\prime}=\{0^{n}\}\mathbin{\circledast}H$ . Extending their techniques, we now show that if $H_{\vee}$ and $H_{\wedge}$ are an $\varepsilon_{\vee}$ -hitting set for width- $w$ $\vee$ -programs and an $\varepsilon_{\wedge}$ -hitting set for width- $w$ $\wedge$ -programs, respectively, then $\{0^{n}\}\mathbin{\circledast}H_{\vee}\mathbin{\circledast}H_{\wedge}$ is an $(\varepsilon_{\vee}+\varepsilon_{\wedge})$ -hitting set for width- $(w+1)$ standard-order ROBPs.

Lemma 4.5 (Simulating width- $(w+1)$ programs using $\vee$ -programs and $\wedge$ -programs of width $w$ ).

Let $\varepsilon_{\vee},\varepsilon_{\wedge}>0$ . For every width- $(w+1)$ standard-order ROBP $f$ with $\operatorname*{\mathbb{E}}[f]>\varepsilon_{\vee}+\varepsilon_{\wedge}$ , there is a set $\mathcal{B}_{f}^{\vee}$ of width- $w$ length- $n$ $\vee$ -programs and a set $\mathcal{B}_{f}^{\wedge}$ of width- $w$ length- $n$ $\wedge$ -programs such that the following hold.

1.

$|\mathcal{B}_{f}^{\vee}|=w+1$ and $|\mathcal{B}_{f}^{\wedge}|\leq n$ .
2.

$\operatorname*{\mathbb{E}}[a]>\varepsilon_{\vee}$ for every $a\in\mathcal{B}_{f}^{\vee}$ and $\operatorname*{\mathbb{E}}[h]>\varepsilon_{\wedge}$ for every $h\in\mathcal{B}_{f}^{\wedge}$ .
3.

For every $z\in\{0,1\}^{n}$ , for every $H_{\vee}\subseteq\{0,1\}^{n}$ such that $H_{\vee}$ hits $\mathcal{B}_{f}^{\vee}$ , and for every $H_{\wedge}\subseteq\{0,1\}^{n}$ such that $H_{\wedge}$ hits $\mathcal{B}_{f}^{\wedge}$ , the set $\{z\}\mathbin{\circledast}H_{\vee}\mathbin{\circledast}H_{\wedge}$ hits $f$ .

In particular, if $H_{\vee}$ is an $\varepsilon_{\vee}$ -hitting set for width- $w$ $\vee$ -programs and $H_{\wedge}$ is an $\varepsilon_{\wedge}$ -hitting set for width- $w$ $\wedge$ -programs, then $\{0^{n}\}\mathbin{\circledast}H_{\vee}\mathbin{\circledast}H_{\wedge}$ hits $f$ .

Proof.

Let $V_{0},V_{1},\dots,V_{n}$ be the layers of $f$ . We assume without loss of generality that $|V_{i}|>1$ for every $i$ and $|V_{n}|=2$ , with one accepting vertex and one rejecting vertex in $V_{n}$ .

For every $t\in\{0,1,\dots,n\}$ , there is some “good vertex” $u_{t}\in V_{t}$ such that $p_{u_{t}\to}\geq\operatorname*{\mathbb{E}}[f]>\varepsilon_{\vee}+\varepsilon_{\wedge}$ . Let $i_{*}+1$ be the smallest value such that there is some “bad vertex” $v_{i_{*}+1}\in V_{i_{*}+1}$ satisfying $p_{v_{i_{*}+1}\to}\leq\varepsilon_{\vee}$ . The existence of this first bad vertex implies that for every $t\in\{i_{*}+2,\dots,n\}$ , there is another bad vertex $v_{t}\in V_{t}$ satisfying $p_{v_{t}\to}\leq\varepsilon_{\vee}$ .

In brief, our strategy is as follows. We will take the first $i_{*}$ steps arbitrarily; there is no risk of hitting a bad vertex during this time. Then, we will use $H_{\vee}$ to reach one of the good vertices ( $u_{t}$ ). Afterward, we will use $H_{\wedge}$ to avoid the bad vertices ( $v_{t}$ ).

In more detail, for each $v\in V_{i_{*}}$ , define $a_{v}\colon\{0,1\}^{n}\to\{0,1\}$ by letting $a_{v}(x)=1$ if and only if there is a value $j\in\{i_{*},\dots,n\}$ such that $f_{v\to}(x)$ visits the good vertex $u_{j}$ . Note that we think of $f_{v\to}$ as a function on $n$ bits that ignores its first $i_{*}$ many input bits. Observe that $a_{v}$ can be computed by a width- $w$ length- $n$ $\vee$ -program. (We can delete the vertices $u_{i_{*}},u_{i_{*}+1},\dots,u_{n}$ , redirect their incoming edges arbitrarily, and mark those edges as accepting edges. Layers $0,1,\dots,i_{*}-1$ can have width $1$ , because that phase of the computation is trivial.) The definition of $i_{*}$ implies that $\operatorname*{\mathbb{E}}[f_{v\to}]>\varepsilon_{\wedge}$ . The final good vertex $u_{n}$ is the accepting vertex, so $\operatorname*{\mathbb{E}}[a_{v}]>\varepsilon_{\vee}$ . Let $\mathcal{B}_{f}^{\vee}=\{a_{v}:v\in V_{i_{*}}\}$ .

Furthermore, for each $j\in\{i_{*},i_{*}+1,\dots,n\}$ , define $h_{j}\colon\{0,1\}^{n}\to\{0,1\}$ by letting $h_{j}(x)=1$ if and only if $f_{u_{j}\to}(x)$ avoids all of the bad vertices $v_{j+1},v_{j+2},\dots,v_{n}$ . Observe that $h_{j}$ can be computed by a width- $w$ length- $n$ $\wedge$ -program. (We can delete the vertices $v_{j+1},v_{j+2},\dots,v_{n}$ , redirect their incoming edges arbitrarily, and mark those edges as rejecting edges. Layers $0,\dots,j$ can have width $1$ , because that phase of the computation is trivial.) Furthermore,

$\displaystyle\operatorname*{\mathbb{E}}[h_{j}]$	$\displaystyle=\Pr_{x\sim U_{n}}[f_{u_{j}\to}(x)\text{ does not visit }v_{j+1},% \dots,v_{n}]$
	$\displaystyle=\Pr_{x\sim U_{n}}[f_{u_{j}\to}(x)=1\text{ and }f_{u_{j}\to}(x)% \text{ does not visit }v_{j+1},\dots,v_{n}]$
	$\displaystyle=p_{u_{j}\to}-\Pr_{x\sim U_{n}}[f_{u_{j}\to}(x)=1\text{ and }f_{u% _{j}\to}(x)\text{ visits at least one of }v_{j+1},\dots,v_{n}]$
	$\displaystyle=p_{u_{j}\to}-\sum_{t=j+1}^{n-1}\Pr[f_{u_{j}\to}(x)=1\text{ and }% f_{u_{j}\to}(x)\text{ visits }v_{t}\text{ but not }v_{j+1},\dots,v_{t-1}]$
	$\displaystyle\geq p_{u_{j}\to}-\sum_{t=j+1}^{n-1}\Pr[f_{u_{j}\to}(x)\text{ % visits }v_{t}\text{ but not }v_{j+1},\dots,v_{t-1}]\cdot\varepsilon_{\vee}$	(1)
	$\displaystyle\geq p_{u_{j}\to}-\varepsilon_{\vee}$
	$\displaystyle>\varepsilon_{\wedge}.$

(Equation 1 holds because the probability that $f_{u_{j}\to}(x)$ accepts conditioned on visiting $v_{t}$ without visiting $v_{j+1},\dots,v_{t-1}$ is precisely $p_{v_{t}\to}$ , which is at most $\varepsilon_{\vee}$ .) Let $\mathcal{B}_{f}^{\wedge}=\{h_{i_{*}},\dots,h_{n}\}$ .

Finally, let $z\in\{0,1\}^{n}$ and let $H_{\vee},H_{\wedge}\subseteq\{0,1\}^{n}$ be sets that hit $\mathcal{B}_{f}^{\vee}$ and $\mathcal{B}_{f}^{\wedge}$ respectively. We must show that $\{z\}\mathbin{\circledast}H_{\vee}\mathbin{\circledast}H_{\wedge}$ hits $f$ . Since $H_{\vee}$ hits $\mathcal{B}_{f}^{\vee}$ , there is some $x\in H_{\vee}$ and some $j_{*}$ such that $f(z_{1\dots i_{*}}x_{i_{*}+1\dots n})$ visits $u_{j_{*}}$ . Since $H_{\wedge}$ hits $\mathcal{B}_{f}^{\wedge}$ , there is some $y\in H_{\wedge}$ such that $h_{j_{*}}(y)=1$ , i.e., $f_{u_{j_{*}}\to}(y)$ avoids all of the bad vertices $v_{j+1},\dots,v_{n}$ . Consequently,

f(z_{1\dots i_{*}}x_{i_{*}+1\dots j_{*}}y_{j_{*}+1\dots n})=1.\

$\hfill\blacktriangleleft$

4.4 Error Reduction

At this point, given an $(\alpha/n)$ -PRG for width- $w$ programs, we have shown how to construct a $(1/2-\Omega(1))$ -HSG for width- $(w+1)$ programs. To construct an $\varepsilon$ -HSG where $\varepsilon$ is small, we will use a version of an error reduction technique introduced by Hoza and Zuckerman [20]. We rely on the following lemma, which shows how to split a branching program into two subprograms, each of which has much higher acceptance probability.

Lemma 4.6 (Increasing a branching program’s acceptance probability).

Let $w,n\in\mathbb{N}$ , let $K\in(1,\infty)$ , and let $f$ be a width- $(w+1)$ length- $n$ standard-order ROBP with $\operatorname*{\mathbb{E}}[f]=p\leq 1/K$ . Let $V$ be the set of vertices in $f$ and let $S$ be the set of vertices $v\in V$ such that $p_{v\to}\geq Kp$ . For each $x\in\{0,1\}^{n}$ , let $g(x)\in\{0,1\}$ indicate whether $f(x)$ visits at least one vertex in $S$ . Then:

1.

The function $g$ can be computed by a width- $(w+1)$ standard-order ROBP.
2.

$\operatorname*{\mathbb{E}}[g]>1/(2K)$ .

Proof sketch.

Observe that if $S$ intersects a layer of $f$ , then $S$ also intersects all subsequent layers of $f$ . Therefore, to construct a program that computes $g$ , we can redirect all outgoing edges from vertices in $S$ to other vertices in $S$ , and then in the final layer, label the vertices in $S$ as accepting and all other vertices as rejecting. Finally, the fact that $\operatorname*{\mathbb{E}}[g]>1/(2K)$ was proven by Bogdanov, Hoza, Prakriya, and Pyne [3, Lemma 25].⁷⁷7Bogdanov, Hoza, Prakriya, and Pyne state the bound as $\operatorname*{\mathbb{E}}[g]\geq 1/(2K)$ [3], but their proof establishes the strict inequality $\operatorname*{\mathbb{E}}[g]>1/(2K)$ . $\hfill\blacktriangleleft$

Given Lemma 4.6, the following error reduction lemma readily follows.

Lemma 4.7 (Error reduction).

Let $w,n\in\mathbb{N}$ , let $\gamma\in(0,1/2)$ , let $\varepsilon\in(0,1)$ , and let $t=\lceil\frac{\ln(1/\varepsilon)}{2\gamma}\rceil$ . For every width- $(w+1)$ length- $n$ standard-order ROBP $f$ such that $\operatorname*{\mathbb{E}}[f]>\varepsilon$ , there is a set $\mathcal{C}_{f}$ of width- $(w+1)$ length- $n$ standard-order ROBPs such that the following hold.

1.

$|\mathcal{C}_{f}|\leq(w+1)\cdot n$ .
2.

$\operatorname*{\mathbb{E}}[g]>1/2-\gamma$ for every $g\in\mathcal{C}_{f}$ .
3.

For any set $H\subseteq\{0,1\}^{n}$ , if $H$ hits $\mathcal{C}_{f}$ , then $H^{\mathbin{\circledast}t}$ hits $f$ .

In particular, if $H$ is a $(1/2-\gamma)$ -hitting set for width- $(w+1)$ length- $n$ standard-order ROBPs, then $H^{\mathbin{\circledast}t}$ hits $f$ .

Proof.

Let $K=\frac{1}{1-2\gamma}$ . Let $V_{0},V_{1},\dots,V_{n}$ be the layers of $f$ . For every vertex $u\in V_{0}\cup\dots\cup V_{n-1}$ , we will define a function $g_{u}\colon\{0,1\}^{n}\to\{0,1\}$ . The definition is as follows.

$\blacksquare$

First, suppose $p_{u\to}>1-2\gamma$ . In this case, we let $g_{u}=f_{u\to}$ .
$\blacksquare$

Now, suppose $p_{u\to}\leq 1-2\gamma$ . Let $S$ be the set of vertices $v$ in layers beyond $u$ such that $p_{v\to}\geq K\cdot p_{u\to}$ . Let $g_{u}(x)$ indicate whether $f_{u\to}(x)$ visits at least one vertex in $S$ .

Lemma 4.6 ensures that $\operatorname*{\mathbb{E}}[g_{u}]>1/(2K)=1/2-\gamma$ and $g_{u}$ can be computed by a width- $(w+1)$ standard-order ROBP. Let $\mathcal{C}_{f}=\{g_{u}:u\in V_{0}\cup\dots\cup V_{n-1}\}$ .

Now let $H$ be a set that hits $\mathcal{C}_{f}$ . We must show that $H^{\mathbin{\circledast}t}$ hits $f$ . By inductively applying the definition of $\mathcal{C}_{f}$ , we see that there is some $x\in H^{\mathbin{\circledast}t}$ such that $f(x)$ visits some vertex $v$ such that $p_{v\to}\geq\min\{1,K^{t}\cdot\varepsilon\}$ . By our choices of $K$ and $t$ , we have

\varepsilon\cdot K^{t}\geq\varepsilon\cdot\left(\frac{1}{1-2\gamma}\right)^{% \ln(1/\varepsilon)/(2\gamma)}\geq\varepsilon\cdot\left(\frac{1}{e^{-2\gamma}}% \right)^{\ln(1/\varepsilon)/(2\gamma)}=1,

so $p_{v_{t}\to}=1$ . Therefore, $f(x)=1$ . $\hfill\blacktriangleleft$

4.5 The Sampler Trick

Combining the lemmas above yields the following.

Theorem 4.8 (If $X$ fools width $w$ , then $\operatorname{Supp}(X)^{\mathbin{\circledast}k}$ hits width $w+1$ ).

Let $w\in\mathbb{N}$ and $\beta>0$ be constants, and assume $e^{\beta-1}+\beta<1/2$ . For every $n\in\mathbb{N}$ and $\varepsilon>0$ , there is a value $k=O(\log(1/\varepsilon))$ such that for every width- $(w+1)$ length- $n$ standard-order ROBP such that $\operatorname*{\mathbb{E}}[f]>\varepsilon$ , there is a set $\mathcal{D}_{f}$ of width- $w$ length- $n$ standard-order ROBPs such that the following hold.

1.

$|\mathcal{D}_{f}|\leq O(n^{3})$ .
2.

If $X$ is a distribution over $\{0,1\}^{n}$ that fools $\mathcal{D}_{f}$ with error $\beta/n$ , then $\operatorname{Supp}(X)^{\mathbin{\circledast}k}$ hits $f$ .

In particular, if $X$ fools all width- $w$ standard-order ROBPs with error $\beta/n$ , then $\operatorname{Supp}(X)^{\mathbin{\circledast}k}$ hits $f$ .

Proof.

Let $\varepsilon_{\wedge}=e^{\beta-1}$ , let $\varepsilon_{\vee}=\beta$ , let $\gamma=\frac{1}{2}-\varepsilon_{\wedge}-\varepsilon_{\vee}>0$ , and let $t=\lceil\frac{\ln(1/\varepsilon)}{2\gamma}\rceil$ . Let $\mathcal{C}_{f}$ be the set from Lemma 4.7. For each $g\in\mathcal{C}_{f}$ , let $\mathcal{B}_{g}^{\vee},\mathcal{B}_{g}^{\wedge}$ be the sets from Lemma 4.5. Let $\mathcal{B}_{\vee}=\bigcup_{g\in\mathcal{C}_{f}}\mathcal{B}_{g}^{\vee}$ and $\mathcal{B}_{\wedge}=\bigcup_{g\in\mathcal{C}_{f}}\mathcal{B}_{g}^{\wedge}$ . For every $a\in\mathcal{B}_{\vee}$ , let $g_{a}$ be the program from Lemma 4.3. For every $h\in\mathcal{B}_{\wedge}$ , let $\mathcal{A}_{h}$ be the set from Corollary 4.2. Let $\mathcal{D}_{f}=\{g_{a}:a\in\mathcal{B}_{\vee}\}\cup\bigcup_{h\in\mathcal{B}_{% \wedge}}\mathcal{A}_{h}$ .

Let us confirm the cardinality bound. We have $|\mathcal{C}_{f}|\leq O(n)$ . For each $g\in\mathcal{C}_{f}$ , we have $|\mathcal{B}_{g}^{\vee}|=w+1$ and $|\mathcal{B}_{g}^{\wedge}|\leq n$ ; therefore, $|\mathcal{B}_{\vee}|\leq O(wn)$ and $|\mathcal{B}_{\wedge}|\leq O(n^{2})$ . For each $h\in\mathcal{B}_{\wedge}$ , we have $|\mathcal{A}_{h}|=n$ ; therefore, $|\mathcal{D}_{f}|\leq O(wn)+O(n^{3})=O(n^{3})$ since $w$ is a constant.

Now suppose $X$ is a distribution over $\{0,1\}^{n}$ that fools $\mathcal{D}_{f}$ with error $\beta/n$ . By Corollary 4.2, $\operatorname{Supp}(X)$ is an $\varepsilon_{\wedge}$ -hitting set for $\mathcal{B}_{\wedge}$ . By Lemma 4.3, $\operatorname{Supp}(X)$ is an $\varepsilon_{\vee}$ -hitting set for $\mathcal{B}_{\vee}$ . Therefore, by Lemma 4.5, $\operatorname{Supp}(X)^{\mathbin{\circledast}3}$ is a $(1/2-\gamma)$ -hitting set for $\mathcal{C}_{f}$ . Finally, applying Lemma 4.7, we conclude that $(\operatorname{Supp}(X)^{\mathbin{\circledast}3})^{\mathbin{\circledast}t})=% \operatorname{Supp}(X)^{\mathbin{\circledast}3t}$ hits $f$ . $\hfill\blacktriangleleft$

At this point, we are nearly done with the proof of Theorem 1.7. Applying Theorem 4.8 directly would lead to a seed length of $O(s(n)\cdot\log(1/\varepsilon))$ . To achieve the superior seed length $O(s(n)+\log n\cdot\log(1/\varepsilon))$ , we use the so-called “sampler trick.” This trick, which was perhaps first used in the context of PRGs by Armoni [1], is based on the concept of an averaging sampler, defined as follows.

Definition 4.9 (Sampler).

Let $\varepsilon,\delta\in(0,1)$ . An $(\varepsilon,\delta)$ -sampler is a function $\mathsf{Samp}\colon\{0,1\}^{\ell}\times\{0,1\}^{d}\to\{0,1\}^{s}$ such that for every function $\phi\colon\{0,1\}^{s}\to\{0,1\}^{n}$ , we have

\Pr_{x\sim U_{\ell}}\left[\left|\operatorname*{\mathbb{E}}[\phi]-\operatorname% *{\mathbb{E}}[\phi(\mathsf{Samp}(x,U_{s}))]\right|\leq\varepsilon\right]\geq 1% -\delta.

We need an explicit sampler with good parameters. The following recent construction, by Xun and Zuckerman [34], is more than sufficient for our purposes.

Theorem 4.10 ([34]).

For every $s\in\mathbb{N}$ and every $\varepsilon,\delta\in(0,1)$ , there exists an explicit $(\varepsilon,\delta)$ -sampler $\mathsf{Samp}\colon\{0,1\}^{\ell}\times\{0,1\}^{d}\to\{0,1\}^{s}$ with $\ell=O(s+\log(1/\delta))$ and $d=O(\log(1/\varepsilon)+\log\log(1/\delta))$ .

Proof of Theorem 1.7.

Let $G\colon\{0,1\}^{s}\to\{0,1\}^{n}$ be the given PRG. Let $\alpha^{\prime}>0$ be a constant small enough that $e^{\alpha+\alpha^{\prime}-1}+\alpha+\alpha^{\prime}<1/2$ ,⁸⁸8This is satisfied provided $\alpha+\alpha^{\prime}<\alpha_{*}\approx 0.095$ . and let $\beta=\alpha+\alpha^{\prime}$ . Let $\varepsilon_{\mathsf{Samp}}=\alpha^{\prime}/n$ , and let $\mathsf{Samp}\colon\{0,1\}^{\ell}\times\{0,1\}^{d}\to\{0,1\}^{s}$ be the $(\varepsilon_{\mathsf{Samp}},\delta_{\mathsf{Samp}})$ -sampler from Theorem 4.10, where $\delta_{\mathsf{Samp}}$ will be specified later.

Let $k=O(\log(1/\varepsilon))$ be the value from Theorem 4.8. For each $x\in\{0,1\}^{\ell}$ , let $G_{x}=G(\mathsf{Samp}(x,U_{d}))$ . Our hitting set is given by

H=\bigcup_{x\in\{0,1\}^{\ell}}\operatorname{Supp}(G_{x})^{\mathbin{\circledast% }k}.

Let us prove that this works. Let $f$ be a width- $(w+1)$ standard-order ROBP such that $\operatorname*{\mathbb{E}}[f]>\varepsilon$ . Let $\mathcal{D}_{f}$ be the set from Theorem 4.8. For each $g\in\mathcal{D}_{f}$ , we define $\phi_{g}\colon\{0,1\}^{s}\to\{0,1\}$ by $\phi_{g}(z)=g(G(z))$ . We choose $\delta_{\mathsf{Samp}}=\Theta(1/n^{3})$ such that $\delta_{\mathsf{Samp}}<1/|\mathcal{D}_{f}|$ . That way, by the sampler definition and the union bound, there exists some $x_{*}\in\{0,1\}^{\ell}$ such that for every $g\in\mathcal{D}_{f}$ , we have

|\operatorname*{\mathbb{E}}[\phi_{g}]-\operatorname*{\mathbb{E}}[\phi_{g}(% \mathsf{Samp}(x_{*},U_{s}))]|\leq\varepsilon_{\mathsf{Samp}}=\alpha^{\prime}/n.

Since $G$ fools $g$ with error $\alpha/n$ , we have $|\operatorname*{\mathbb{E}}[\phi_{g}]-\operatorname*{\mathbb{E}}[g]|\leq\alpha/n$ . Therefore, $G_{x_{*}}$ fools $g$ with error $\beta/n$ . By Theorem 4.8, it follows that $\operatorname{Supp}(G_{x_{*}})^{\mathbin{\circledast}k}$ hits $f$ .

The seed length of our HSG is $\ell+k\cdot(d+\log n)$ , which is $O(s+\log n\cdot\log(1/\varepsilon))$ as promised. $\hfill\blacktriangleleft$

References

[1] Roy Armoni. On the derandomization of space-bounded computations. In Proceedings of the 2nd Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 47–59, 1998. doi:10.1007/3-540-49543-6_5.
[2] Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width-2 branching programs. Theory Comput., 9:283–292, 2013. doi:10.4086/toc.2013.v009a007.
[3] Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne. Hitting Sets for Regular Branching Programs. In Proceedings of the 37th Computational Complexity Conference (CCC), pages 3:1–3:22, 2022. doi:10.4230/LIPIcs.CCC.2022.3.
[4] Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM J. Comput., 49(5):STOC18–242–STOC18–299, 2020. doi:10.1137/18M1197734.
[5] Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973–986, 2014. doi:10.1137/120875673.
[6] Joshua Brody and Elad Verbin. The coin problem, and pseudorandomness for branching programs. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 30–39, 2010. doi:10.1109/FOCS.2010.10.
[7] Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Improved algorithms via approximations of probability distributions. J. Comput. System Sci., 61(1):81–107, 2000. doi:10.1006/jcss.1999.1695.
[8] Eshan Chattopadhyay and Jyun-Jie Liao. Recursive Error Reduction for Regular Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS), pages 29:1–29:20, 2024. doi:10.4230/LIPIcs.ITCS.2024.29.
[9] Ben Chen and Amnon Ta-Shma. Better weighted pseudorandom generators against low weight read-once branching programs. ECCC preprint TR25-067, 2025. URL: https://eccc.weizmann.ac.il/report/2025/067/.
[10] Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, and Hongxun Wu. Weighted pseudorandom generators via inverse analysis of random walks and shortcutting. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1224–1239, 2023. doi:10.1109/FOCS57990.2023.00072.
[11] Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Theory Comput., 18:Paper No. 21, 32, 2022. doi:10.4086/toc.2022.v018a021.
[12] Kuan Cheng and Ruiyang Wu. Weighted pseudorandom generators for read-once branching programs via weighted pseudorandom reductions. ECCC preprint TR25-027, 2025. URL: https://eccc.weizmann.ac.il/report/2025/027/.
[13] Anindya De. Pseudorandomness for permutation and regular branching programs. In 26th Annual Conference on Computational Complexity (CCC), pages 221–231, 2011. doi:10.1109/CCC.2011.23.
[14] Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM), pages 504–517, 2010. doi:10.1007/978-3-642-15369-3_38.
[15] Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 120–129, 2012. doi:10.1109/FOCS.2012.77.
[16] Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024. doi:10.1561/0400000109.
[17] William M. Hoza. Recent progress on derandomizing space-bounded computation. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 138:114–143, 2022. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/728.
[18] William M. Hoza, Edward Pyne, and Salil Vadhan. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. In 12th Innovations in Theoretical Computer Science Conference (ITCS), pages 7:1–7:20, 2021. doi:10.4230/LIPIcs.ITCS.2021.7.
[19] William M. Hoza, Edward Pyne, and Salil Vadhan. Limitations of the Impagliazzo–Nisan–Wigderson pseudorandom generator against permutation branching programs. Algorithmica, 2024. doi:10.1007/s00453-024-01251-2.
[20] William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success $\mathbf{RL}$ . SIAM J. Comput., 49(4):811–820, 2020. doi:10.1137/19M1268707.
[21] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual Symposium on Theory of Computing (STOC), pages 356–364, 1994. doi:10.1145/195058.195190.
[22] Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák. Pseudorandom generators for group products [extended abstract]. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 263–272, 2011. doi:10.1145/1993636.1993672.
[23] Vinayak M. Kumar. New Pseudorandom Generators and Correlation Bounds Using Extractors. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325, pages 68:1–68:23, 2025. doi:10.4230/LIPIcs.ITCS.2025.68.
[24] Chin Ho Lee, Edward Pyne, and Salil Vadhan. On the Power of Regular and Permutation Branching Programs. In Proceedings of the 27th International Conference on Randomization and Computation (RANDOM), pages 44:1–44:22, 2023. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.44.
[25] Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Proceedings of the 51st Annual Symposium on Theory of Computing (STOC), pages 626–637, 2019. doi:10.1145/3313276.3316319.
[26] Augusto Modanese. Pseudorandom generators for sliding-window algorithms. arXiv preprint 2301.07384, 2023. doi:10.48550/arXiv.2301.07384.
[27] Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. doi:10.1137/0222053.
[28] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. doi:10.1007/BF01305237.
[29] Edward Pyne, Ran Raz, and Wei Zhan. Certified hardness vs. randomness for log-space. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 989–1007, 2023. doi:10.1109/FOCS57990.2023.00061.
[30] Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). In Proceedings of the 36th Computational Complexity Conference (CCC), pages 33:1–33:15, 2021. doi:10.4230/LIPIcs.CCC.2021.33.
[31] Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the $\bf RL$ vs. $\bf L$ problem. In Proceedings of the 38th Annual Symposium on Theory of Computing (STOC), pages 457–466, 2006. doi:10.1145/1132516.1132583.
[32] Michael Saks and David Zuckerman, 1995. Unpublished.
[33] Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. ECCC preprint TR12-083, 2012. URL: https://eccc.weizmann.ac.il/report/2012/083/.
[34] Zhiyang Xun and David Zuckerman. Near-optimal averaging samplers and matrix samplers. ECCC preprint TR24-097, 2024. URL: https://eccc.weizmann.ac.il/report/2024/097/.

[bib.bib1] [1] Roy Armoni. On the derandomization of space-bounded computations. In Proceedings of the 2nd Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 47–59, 1998. doi:10.1007/3-540-49543-6_5.

[bib.bib2] [2] Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width-2 branching programs. Theory Comput., 9:283–292, 2013. doi:10.4086/toc.2013.v009a007.

[bib.bib3] [3] Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne. Hitting Sets for Regular Branching Programs. In Proceedings of the 37th Computational Complexity Conference (CCC), pages 3:1–3:22, 2022. doi:10.4230/LIPIcs.CCC.2022.3.

[bib.bib4] [4] Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM J. Comput., 49(5):STOC18–242–STOC18–299, 2020. doi:10.1137/18M1197734.

[bib.bib5] [5] Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973–986, 2014. doi:10.1137/120875673.

[bib.bib6] [6] Joshua Brody and Elad Verbin. The coin problem, and pseudorandomness for branching programs. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 30–39, 2010. doi:10.1109/FOCS.2010.10.

[bib.bib7] [7] Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Improved algorithms via approximations of probability distributions. J. Comput. System Sci., 61(1):81–107, 2000. doi:10.1006/jcss.1999.1695.

[bib.bib8] [8] Eshan Chattopadhyay and Jyun-Jie Liao. Recursive Error Reduction for Regular Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS), pages 29:1–29:20, 2024. doi:10.4230/LIPIcs.ITCS.2024.29.

[bib.bib9] [9] Ben Chen and Amnon Ta-Shma. Better weighted pseudorandom generators against low weight read-once branching programs. ECCC preprint TR25-067, 2025. URL: https://eccc.weizmann.ac.il/report/2025/067/.

[bib.bib10] [10] Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, and Hongxun Wu. Weighted pseudorandom generators via inverse analysis of random walks and shortcutting. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1224–1239, 2023. doi:10.1109/FOCS57990.2023.00072.

[bib.bib11] [11] Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Theory Comput., 18:Paper No. 21, 32, 2022. doi:10.4086/toc.2022.v018a021.

[bib.bib12] [12] Kuan Cheng and Ruiyang Wu. Weighted pseudorandom generators for read-once branching programs via weighted pseudorandom reductions. ECCC preprint TR25-027, 2025. URL: https://eccc.weizmann.ac.il/report/2025/027/.

[bib.bib13] [13] Anindya De. Pseudorandomness for permutation and regular branching programs. In 26th Annual Conference on Computational Complexity (CCC), pages 221–231, 2011. doi:10.1109/CCC.2011.23.

[bib.bib14] [14] Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM), pages 504–517, 2010. doi:10.1007/978-3-642-15369-3_38.

[bib.bib15] [15] Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 120–129, 2012. doi:10.1109/FOCS.2012.77.

[bib.bib16] [16] Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024. doi:10.1561/0400000109.

[bib.bib17] [17] William M. Hoza. Recent progress on derandomizing space-bounded computation. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 138:114–143, 2022. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/728.

[bib.bib18] [18] William M. Hoza, Edward Pyne, and Salil Vadhan. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. In 12th Innovations in Theoretical Computer Science Conference (ITCS), pages 7:1–7:20, 2021. doi:10.4230/LIPIcs.ITCS.2021.7.

[bib.bib19] [19] William M. Hoza, Edward Pyne, and Salil Vadhan. Limitations of the Impagliazzo–Nisan–Wigderson pseudorandom generator against permutation branching programs. Algorithmica, 2024. doi:10.1007/s00453-024-01251-2.

[bib.bib20] [20] William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success $\mathbf{RL}$ . SIAM J. Comput., 49(4):811–820, 2020. doi:10.1137/19M1268707.

[bib.bib21] [21] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual Symposium on Theory of Computing (STOC), pages 356–364, 1994. doi:10.1145/195058.195190.

[bib.bib22] [22] Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák. Pseudorandom generators for group products [extended abstract]. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 263–272, 2011. doi:10.1145/1993636.1993672.

[bib.bib23] [23] Vinayak M. Kumar. New Pseudorandom Generators and Correlation Bounds Using Extractors. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325, pages 68:1–68:23, 2025. doi:10.4230/LIPIcs.ITCS.2025.68.

[bib.bib24] [24] Chin Ho Lee, Edward Pyne, and Salil Vadhan. On the Power of Regular and Permutation Branching Programs. In Proceedings of the 27th International Conference on Randomization and Computation (RANDOM), pages 44:1–44:22, 2023. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.44.

[bib.bib25] [25] Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Proceedings of the 51st Annual Symposium on Theory of Computing (STOC), pages 626–637, 2019. doi:10.1145/3313276.3316319.

[bib.bib26] [26] Augusto Modanese. Pseudorandom generators for sliding-window algorithms. arXiv preprint 2301.07384, 2023. doi:10.48550/arXiv.2301.07384.

[bib.bib27] [27] Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. doi:10.1137/0222053.

[bib.bib28] [28] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. doi:10.1007/BF01305237.

[bib.bib29] [29] Edward Pyne, Ran Raz, and Wei Zhan. Certified hardness vs. randomness for log-space. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 989–1007, 2023. doi:10.1109/FOCS57990.2023.00061.

[bib.bib30] [30] Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). In Proceedings of the 36th Computational Complexity Conference (CCC), pages 33:1–33:15, 2021. doi:10.4230/LIPIcs.CCC.2021.33.

[bib.bib31] [31] Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the $\bf RL$ vs. $\bf L$ problem. In Proceedings of the 38th Annual Symposium on Theory of Computing (STOC), pages 457–466, 2006. doi:10.1145/1132516.1132583.

[bib.bib32] [32] Michael Saks and David Zuckerman, 1995. Unpublished.

[bib.bib33] [33] Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. ECCC preprint TR12-083, 2012. URL: https://eccc.weizmann.ac.il/report/2012/083/.

[bib.bib34] [34] Zhiyang Xun and David Zuckerman. Near-optimal averaging samplers and matrix samplers. ECCC preprint TR24-097, 2024. URL: https://eccc.weizmann.ac.il/report/2024/097/.

Implications of Better PRGs for Permutation Branching Programs

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1.1 (PRGs).

Definition 1.2 (ROBPs).

1.1 Regular and Permutation Branching Programs

Definition 1.3 (Regular and permutation ROBPs).

1.2 Width-𝟐, Width-𝟑, and Width-𝟒 Branching Programs

1.3 Hitting Set Generators

Definition 1.4 (HSGs).

1.4 Our Contributions

Theorem 1.5 (PRGs for width-6 permutation programs ⟹ HSGs for width-4 programs).

Theorem 1.6 (Fooling width-6 permutation programs ⟹ fooling width-3 programs).

Theorem 1.7 (PRGs for width-w programs ⟹ HSGs for width-(w+1) programs).

Proof of Theorem 1.5, given Theorems 1.6 and 1.7.

1.5 Context: Weighted Pseudorandom Generators

Definition 1.8 (WPRGs).

1.6 Techniques

Definition 1.9 (∧-programs and ∨-programs).

1.6.1 Near-Permutation Programs vs. Exact Permutation Programs

1.6.2 Using a PRG for Width 𝒘 to Design an HSG for Width 𝒘+𝟏

1.7 Organization

2 Preliminaries

2.1 Subprograms, Substrings, Hitting Sets, and Restrictions

2.2 Probability

Lemma 2.1 (Sandwiching lemma).

Proof.

Lemma 2.2 (Reverse union bound).

Proof.

3 Conditional Low-Error PRGs for Width-𝟑 ROBPs

3.1 Fooling Programs That Have a Few Colliding Layers

Lemma 3.1 (Fooling permutation ∧-programs [3]).

Definition 3.2 (Colliding layer).

Lemma 3.3 (Fooling ∧-programs with a few colliding layers).

Proof.

Definition 3.4 ((w,t,ε)-program).

Lemma 3.5 (Fooling ∧-programs with t colliding layers ⟹ fooling (w,t,ε)-programs).

Proof.

3.2 Reducing the Number of Colliding Layers in a Width-𝟑 Program

Lemma 3.6 (Restrictions for width-3 programs [25, 10]).

Proof sketch of Lemma 3.6.

Proof of Theorem 1.6.

4 Conditional HSGs for Width-𝟒 ROBPs

4.1 Hitting Width-𝒘 ∧-Programs

Lemma 4.1 (Expected number of rejecting edges traversed in an ∧-program).

Proof.

Corollary 4.2 (PRGs for width-w ROBPs are HSGs for width-w ∧-programs).

Proof.

4.2 Hitting Width-𝒘 ∨-Programs

Lemma 4.3 (HSGs for width-w ROBPs are also HSGs for width-w ∨-programs).

Proof.

4.3 Hitting Width-(𝒘+𝟏) Programs

Definition 4.4 (The ⊛ operation).

Lemma 4.5 (Simulating width-(w+1) programs using ∨-programs and ∧-programs of width w).

Proof.

4.4 Error Reduction

Lemma 4.6 (Increasing a branching program’s acceptance probability).

Proof sketch.

Lemma 4.7 (Error reduction).

Proof.

4.5 The Sampler Trick

Theorem 4.8 (If X fools width w, then Supp(X)⊛k hits width w+1).

Proof.

Definition 4.9 (Sampler).

Theorem 4.10 ([34]).

Proof of Theorem 1.7.

References

1.2 Width- $2$ , Width- $3$ , and Width- $4$ Branching Programs

Theorem 1.5 (PRGs for width- $6$ permutation programs $\implies$ HSGs for width- $4$ programs).

Theorem 1.6 (Fooling width- $6$ permutation programs $\implies$ fooling width- $3$ programs).

Theorem 1.7 (PRGs for width- $w$ programs $\implies$ HSGs for width- $(w+1)$ programs).

Definition 1.9 ( $\wedge$ -programs and $\vee$ -programs).

1.6.2 Using a PRG for Width $𝒘$ to Design an HSG for Width $w+1$

3 Conditional Low-Error PRGs for Width- $3$ ROBPs

Lemma 3.1 (Fooling permutation $\wedge$ -programs [3]).

Lemma 3.3 (Fooling $\wedge$ -programs with a few colliding layers).

Definition 3.4 ( $(w,t,\varepsilon)$ -program).

Lemma 3.5 (Fooling $\wedge$ -programs with $t$ colliding layers $\implies$ fooling $(w,t,\varepsilon)$ -programs).

3.2 Reducing the Number of Colliding Layers in a Width- $3$ Program

Lemma 3.6 (Restrictions for width- $3$ programs [25, 10]).

4 Conditional HSGs for Width- $4$ ROBPs

4.1 Hitting Width- $𝒘$ $\wedge$ -Programs

Lemma 4.1 (Expected number of rejecting edges traversed in an $\wedge$ -program).

Corollary 4.2 (PRGs for width- $w$ ROBPs are HSGs for width- $w$ $\wedge$ -programs).

4.2 Hitting Width- $𝒘$ $\vee$ -Programs

Lemma 4.3 (HSGs for width- $w$ ROBPs are also HSGs for width- $w$ $\vee$ -programs).

4.3 Hitting Width- $(w+1)$ Programs

Definition 4.4 (The $\mathbin{\circledast}$ operation).

Lemma 4.5 (Simulating width- $(w+1)$ programs using $\vee$ -programs and $\wedge$ -programs of width $w$ ).

Theorem 4.8 (If $X$ fools width $w$ , then $\operatorname{Supp}(X)^{\mathbin{\circledast}k}$ hits width $w+1$ ).