On Sums of INW Pseudorandom Generators

Randomness can be considered a type of “fuel” for computation. We prefer to use as little randomness as possible, just like we prefer to minimize consumption of other types of “fuel.” A pseudorandom generator (PRG) is a way of decreasing the number of random bits used in computation.

In this paper, we study PRGs in the context of space-bounded computation. If we wish to simulate a randomized space-bounded algorithm, then we ought to use a PRG that fools standard-order read-once branching programs (ROBPs), defined next.

Polynomial-width standard-order ROBPs describe what log-space randomized algorithms do on a fixed input as a function of their random bits. In this paper, we focus on the constant-width case. There isn’t necessarily a clear connection between constant-width ROBPs and uniform models of computation such as randomized Turing machines, but constant-width ROBPs still constitute an extremely interesting nonuniform model of space-bounded computation. The width-$2$ case is well-understood [44, 4, 19, 29]. In particular, Saks and Zuckerman showed in the 1990s that there is an explicit PRG that fools width-$2$ branching programs with seed length $O(\log n)$ [44], which is optimal. Decades later, Meka, Reingold, and Tal showed that there is an explicit PRG that fools width-$3$ standard-order ROBPs with seed length $\tilde{O}(\log n)$ [35]. However, the best seed length bound for width-$4$ programs is $O({\log }^{2}n)$, which is a special case of the following classic theorem.

The original proof of Theorem 3 is due to Nisan [38]. There is an alternative proof due to Impagliazzo, Nisan, and Wigderson [26] that is more relevant to the present paper. Impagliazzo, Nisan, and Wigderson inductively defined a sequence of PRGs $G_0,G_1,\mathrm{\dots }$, where $G_j:{ℛ}_j\to {\{0,1\}}^{2^j}$, as follows.

1. 1.

   Base case: Let ${ℛ}_0=\{0,1\}$ and $G_0(x)=x$.

2. 2.

   Inductive step: Assume we have already constructed $G_{j-1}$. Let $H_j$ be a $D_j$-regular undirected multigraph on the vertex set ${ℛ}_{j-1}$. Define ${ℛ}_j={ℛ}_{j-1}\times [D_j]$ and

   $$G_j(x,y)=(G_{j-1}(x),G_{j-1}(H_j[x,y])).$$

   Here $H_j[x,y]$ denotes the $y$-th neighbor of the vertex $x$ in $H_j$.

Impagliazzo, Nisan, and Wigderson’s original analysis [26] shows that if $\lambda (H_j)\le \lambda$ for every $j$, then $G_{\log n}$ fools width-$w$ length-$n$ standard-order ROBPs with error $\lambda \cdot w\cdot n$. Here $\lambda (H_j)$ denotes the spectral expansion parameter of $H_j$, which can be defined as the second largest eigenvalue of its transition probability matrix in absolute value. There are numerous explicit constructions of expander graphs $H_j$ such that $\lambda (H_j)\le \lambda$ and $\mathrm{deg}(H_j)\le \mathrm{poly}(1/\lambda )$. (See, for example, Vadhan’s pseudorandomness survey [47].) If we use such expander graphs, then the seed length of $G_{\log n}$ is $O(\log n\cdot \log (1/\lambda ))$. Choosing $\lambda =\frac{\epsilon }{wn}$ completes the proof of Theorem 3.

It is a major open problem to design PRGs that fool constant-width standard-order ROBPs with seed length $o({\log }^{2}n)$. A natural thing to try is to simply increase the parameter $\lambda$ in the INW construction. Indeed, even when $\lambda$ is relatively large, it turns out that the INW generator still does a good job of fooling so-called “regular” and “permutation” ROBPs [8, 15, 28, 45, 22]. More generally, one can try using different values of $\lambda$ at the different levels of the recursion, say ${\lambda }_1,\mathrm{\dots },{\lambda }_{\log n}$. For example, Rozenman and Vadhan showed how to use the INW generator, with ${\lambda }_j=\mathrm{\Omega }(1)$ for most but not all $j$, to solve the undirected $s$-$t$ connectivity problem in deterministic log-space [43], re-proving Reingold’s famous theorem [42].

Unfortunately, it turns out that no matter how we set the expansion parameters, the INW generator is provably too weak to fool constant-width standard-order ROBPs with seed length $o({\log }^{2}n)$ [9, 23]. Making this statement precise is a little subtle, because “the” INW generator is actually a whole family of PRGs, even after we fix the expansion parameters ${\lambda }_1,\mathrm{\dots },{\lambda }_{\log n}$. After all, the definition of the PRG does not specify which specific expander graphs to use. For a vector $\overrightarrow{\lambda }=({\lambda }_1,\mathrm{\dots },{\lambda }_{\log n})$, let us define $\mathrm{INW}(\overrightarrow{\lambda })$ to be the set of all PRGs $G_{\log n}$ that can be constructed via the INW template using graphs $H_1,\mathrm{\dots },H_{\log n}$ satisfying $\lambda (H_j)\le {\lambda }_j$ for every $j$. As a shorthand, let us also write $\mathrm{INW}(\lambda )$ for the special case ${\lambda }_1={\lambda }_2=\mathrm{\cdots }={\lambda }_{\log n}=\lambda$ when $n$ is clear from context. (See Definition 23 for a more detailed definition.) Then we have the following theorem due to Brody and Verbin [9], with details filled in by Hoza, Pyne, and Vadhan [23]:

Theorem 4 can be interpreted as saying that if one wishes to use the INW template to construct a PRG that fools width-$3$ standard-order ROBPs with seed length $o({\log }^{2}n)$, then the proof of correctness would have to exploit some property of the specific graphs $H_1,\mathrm{\dots },H_{\log n}$ beyond their spectral expansion. It is not clear what property would be helpful.

In this paper, we propose a new approach for constructing a near-optimal PRG fooling constant-width standard-order ROBPs. The approach is based on the classic notion of unpredictability. Specialized to the setting of standard-order ROBPs, unpredictability can be defined as follows.

Interestingly, even though $\mathrm{INW}(1/\mathrm{polylog}n)$ does not fool width-$3$ programs (Theorem 4), it turns out that $\mathrm{INW}(1/\mathrm{polylog}n)$ is unpredictable for constant-width programs. More precisely, Fefferman, Shaltiel, Umans, and Viola showed that every PRG in the family $\mathrm{INW}(\lambda )$ is $O(w\cdot \lambda \cdot \log n)$-unpredictable for width-$w$ standard-order ROBPs [16].²²2One way to prove this statement is to use the notion of weight introduced by Braverman, Rao, Raz, and Yehudayoff [8]. For any next-bit predictor $f:{\{0,1\}}^{i-1}\to \{0,1\}$, we can define a test $g:{\{0,1\}}^i\to \{0,1\}$ that checks whether $f$ succeeds: $g(x_1,\mathrm{\dots },x_i)=f(x_1,\mathrm{\dots },x_{i-1})\oplus x_i$. If $f$ can be computed by a width-$w$ standard-order ROBP, then $g$ can be computed by a width-$w$ standard-order ROBP with weight two. From here, Braverman, Rao, Raz, and Yehudayoff’s analysis shows that $\mathrm{INW}(\lambda )$ fools $g$ with error $O(w\cdot \lambda \cdot \log n)$ [8].

How can we leverage the unpredictability of the INW generator to construct a PRG that actually fools constant-width ROBPs? Fefferman, Shaltiel, Umans, and Viola suggested combining the INW generator with a randomness extractor [16]. We propose a different approach, inspired by Yao’s XOR Lemma in circuit complexity. Yao’s XOR Lemma is about the average-case hardness of computing a Boolean function, or more generally the hardness of guessing a Boolean random variable $Y\in \{0,1\}$ given some correlated random variable $X\in {\{0,1\}}^n$. Let $(X^{(1)},Y^{(1)}),\mathrm{\dots },(X^{(t)},Y^{(t)})$ be $t$ independent copies of $(X,Y)$. Roughly speaking, Yao’s XOR Lemma says that if it is “somewhat hard” to guess $Y$ given $X$, then it is “very hard” to guess $Y^{(1)}\oplus \mathrm{\cdots }\oplus Y^{(t)}$ given $X^{(1)},\mathrm{\dots },X^{(t)}$. Here “somewhat hard” means that all small circuits have, e.g., a constant failure probability, and “very hard” means that all small circuits have a failure probability very close to $1/2$.

Maurer and Tessaro observed that Yao’s XOR Lemma implies that the bitwise XOR operation amplifies cryptographic unpredictability [34]. In more detail, let $X$ be a distribution that is $\delta$-unpredictable for small circuits for a relatively large value of $\delta$ such as $\delta =0.1$. Let $X^{\prime }=X^{(1)}\oplus \mathrm{\cdots }\oplus X^{(t)}$, where $X^{(1)},\mathrm{\dots },X^{(t)}$ are independent copies of $X$. Yao’s XOR Lemma implies that if a small circuit attempts to guess the $i$-th bit of $X^{\prime }$ given the first $i-1$ bits of each copy $X^{(1)},\mathrm{\dots },X^{(t)}$, then its success probability will be very close to $1/2$. If the circuit is only given the first $i-1$ bits of $X^{\prime }$, then the prediction task becomes even more difficult. Thus, $X^{\prime }$ is ${\delta }^{\prime }$-unpredictable for small circuits where ${\delta }^{\prime }\ll \delta$.

Intuitively, we expect the same phenomenon to occur in the ROBP setting. If $X^{\prime }$ is the bitwise XOR of $t$ independent copies of some distribution $X$ that is $\delta$-unpredictable for constant-width standard-order ROBPs, then we expect $X^{\prime }$ to be ${\delta }^{\prime }$-unpredictable for such programs, where ${\delta }^{\prime }\approx {\delta }^t$. By Yao’s so-called “distinguisher-to-predictor lemma,” this would imply that $X^{\prime }$ actually fools such programs with error ${\delta }^{\prime }\cdot n$. Based on these considerations, we propose the following two-step approach for constructing near-optimal PRGs fooling constant-width standard-order ROBPs.

• $\mathrm{■}$

  Step 1: Let $G\in \mathrm{INW}(1/\mathrm{polylog}n)$ be a PRG with seed length $s=\tilde{O}(\log n)$. Prove that if we sample $t\approx \log n$ seeds $Z^{(1)},\mathrm{\dots },Z^{(t)}$ independently and uniformly at random, then the bitwise XOR $G(Z^{(1)})\oplus \mathrm{\cdots }\oplus G(Z^{(t)})$ fools constant-width standard-order ROBPs.

• $\mathrm{■}$

  Step 2: Derandomize the proof of Step 1. That is, prove that $G(Z^{(1)})\oplus \mathrm{\cdots }\oplus G(Z^{(t)})$ fools constant-width standard-order ROBPs even if the seeds $Z^{(1)},\mathrm{\dots },Z^{(t)}$ are not independent, but rather they are generated in some pseudorandom manner using only $\tilde{O}(\log n)$ truly random bits.

To be clear, “Step 1” is not in any way trivial, even if we ignore “Step 2.” Taking a bitwise XOR of several independent samples from a distribution does not always improve its pseudorandomness properties. For example, if $X$ is $k$-wise uniform and uniform over a subspace of ${𝔽}_2^n$ (see Section 2.8), then the bitwise XOR of many copies of $X$ has the same distribution as a single copy of $X$. See also Theorem 10.

One of the main results of this paper is to accomplish “Step 1” described above. To state our results more precisely, let us make the following definition.

We prove the following.

For example, Theorem 7 implies that there is a value $t=\mathrm{\Theta }(\frac{\log w\cdot \log n+\log (1/\epsilon )}{\log \log n})$ such that ${\mathrm{INW}}^{\oplus t}(1/{\log }^{2}n)$ fools width-$w$ length-$n$ standard-order ROBPs with error $\epsilon$. By plugging in explicit expanders of degree $\mathrm{poly}(1/\lambda )$, we get an explicit PRG that fools width-$w$ length-$n$ standard-order ROBPs with error $\epsilon$ and seed length

re-proving Theorem 3 in the case $w=O(1)$. For context, prior to our work, there were already several different known ways to construct PRGs that fool constant-width standard-order ROBPs (and more general models) using a seed of length $O({\log }^{2}n)$ [38, 26, 2, 41, 18, 7] or $\tilde{O}({\log }^{2}n)$ [17]. Our Theorem 7 adds to this list.

We hope that there is value in having yet another proof of the $O({\log }^{2}n)$ bound, but of course the real goal is to construct a PRG with seed length $o({\log }^{2}n)$. As discussed previously, we believe that the most promising approach (“Step 2” in our proposal) is to “derandomize” Theorem 7, i.e., prove that a similar error bound holds even if the $t$ seeds for the INW generators are chosen in some pseudorandom manner instead of sampling them independently. So far, we have not figured out how to make such an approach work. However, we would like to point out several “success stories” describing cases in which prior researchers managed to solve similar problems:

• $\mathrm{■}$

  There are known derandomized versions of Yao’s XOR Lemma [25, 27, 12].

• $\mathrm{■}$

  The first asymptotically optimal “small-bias” generator, due to Naor and Naor [37], works by plugging several correlated seeds into a weak initial generator and taking the bitwise XOR of the results [37].

• $\mathrm{■}$

  There are several constructions of low-error “weighted pseudorandom generators” and “hitting set generators” for space-bounded computation that work by plugging several correlated seeds into a “moderate-error” initial PRG and then combining the results in some manner [24, 40, 14, 21, 5, 11, 10, 13].

We find these success stories encouraging.

Instead of analyzing correlated seeds, we can also consider a different and more straightforward approach for improving the seed length of our PRG. What happens if we take an XOR of fewer copies of the INW generator while still using relatively mild expander graphs? For example, what if we try ${\mathrm{INW}}^{\oplus 2}(1/\mathrm{polylog}n)$?

We are inspired to ask this question because of a line of work on the bitwise XOR of small-bias distributions. Recall that by definition, a distribution $X$ over ${\{0,1\}}^n$ is $\epsilon$-biased if, for every nonempty set $S\subseteq [n]$, we have $|\mathrm{Pr}[{\oplus }_{i\in S}{X}_i=0]-\mathrm{Pr}[{\oplus }_{i\in S}{X}_i=1]|\le \epsilon$. A sequence of works has shown that the bitwise XOR of $d$ independent small-bias distributions fools degree-$d$ polynomials over ${𝔽}_2$, whereas the XOR of only $d-1$ small-bias distributions does not (unless the bias parameter is extremely small) [6, 32, 48, 33]. This demonstrates that a bitwise XOR of a small number of “weak” PRGs can sometimes be quite strong. Indeed, the XOR of just two small-bias distributions has been proposed as a candidate PRG for ROBPs [36, 31].

Unfortunately, we prove that ${\mathrm{INW}}^{\oplus 2}(1/\mathrm{polylog}n)$ is not capable of fooling width-$3$ standard-order ROBPs. More generally, no matter how many or how few copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the resulting PRG fools width-$3$ programs, then the seed length is inevitably $\mathrm{\Omega }({\log }^{2}n)$:

Motivated by Theorems 7 and 8, we wish to better understand how our new ${\mathrm{INW}}^{\oplus t}$ generator compares to the classic $\mathrm{INW}$ generator. To be more precise, suppose that for some relatively large value of $\lambda$, it turns out that $\mathrm{INW}(\lambda )$ is too weak to fool some class of functions. To strengthen the PRG, one could try using ${\mathrm{INW}}^{\oplus t}(\lambda )$ for some $t>1$, or one could try using $\mathrm{INW}({\lambda }^{\prime })$ for some . Which approach is better?

We prove that these two approaches are in fact incomparable in general. There are cases in which one approach is better, and there are cases in which the other approach is better. We state these results precisely in the following two theorems. The first theorem describes a case in which summing multiple generators is the better approach.

Item 1 in the theorem above is an immediate consequence of prior work [28, 15, 45, 6, 32, 48]. The main content of the theorem is Item 2. Theorem 9 demonstrates the strength of the “XOR of INW” paradigm. We hope that future researchers can capitalize on the strengths of the ${\mathrm{INW}}^{\oplus t}$ generator to develop better PRGs for ROBPs. Next, let us discuss a case in which summing multiple INW generators is worse than simply using one INW generator with a slightly smaller $\lambda$ value.

Theorem 10 is valuable because it helps us to interpret Theorem 7. As a reminder, Theorem 7 says that constant-width ROBPs are fooled by a sum of $\mathrm{INW}(1/\mathrm{polylog}n)$ generators. In a sense, Theorem 10 shows that Theorem 7 “could have been false” and was not “inevitable.” Indeed, Theorem 10 shows that in general, the fact that a function is fooled by $\mathrm{INW}(1/\mathrm{poly}(n))$ does not automatically imply that it is fooled by a sum of $\mathrm{INW}(1/\mathrm{polylog}n)$ generators. Consequently, Theorem 7 reveals a new weakness of the constant-width ROBP model, above and beyond the well-known weakness of being fooled by $\mathrm{INW}(1/\mathrm{poly}(n))$. We hope that future researchers can further exploit the weaknesses of such programs to fool them with a shorter seed.

It might be instructive to compare ${\mathrm{INW}}^{\oplus t}(\lambda )$ with a different family of PRGs. Let ${𝒢}_t(\lambda )$ denote the set of generators one can construct by the following recursive paradigm:

where $H_{i+1}$ is a graph satisfying $\lambda (H_{i+1})\le \lambda$. This is the same as the definition of the INW generator, except that we use a $t$-th power of an expander graph instead of using a generic expander graph. Then ${𝒢}_t(\lambda )\subseteq \mathrm{INW}({\lambda }^t)$, so a theorem saying “Every PRG in ${𝒢}_t(\lambda )$ fools width-$w$ length-$n$ standard-order ROBPs with error ${\lambda }^t\cdot w\cdot n$” would be true but not interesting. In contrast, Theorem 10 implies that ${\mathrm{INW}}^{\oplus t}(\lambda )⊈\mathrm{INW}({\lambda }^t)$, and we believe that Theorem 7 is saying something new and interesting.

Assadi and N established a general XOR lemma for streaming algorithms [3] (see also work by Lee, Pyne, and Vadhan [30]). However, their XOR lemma does not imply anything about ${\mathrm{INW}}^{\oplus t}$, because they focus on the scenario in which the streaming algorithm sees $t$ instances of a problem in sequence, one after another, instead of seeing the bitwise XOR of the instances.

Several prior works have proved limitations on the power of sums of small-bias distributions to fool various types of tests [6, 33, 36, 4, 31]. Our negative result about using ${\mathrm{INW}}^{\oplus t}$ to fool ROBPs (Theorem 8) is in a similar spirit, and indeed the proof builds on Lee and Viola’s work [31] as mentioned previously.

Ultimately, the model of computation we are interested in is the standard-order ROBP model (Definition 2). At intermediate stages of our argument, we will use a slight generalization of the ROBP model called the “read-once evaluation program” (ROEP) model, introduced by Braveman, Rao, Raz, and Yehudayoff [8]. An ROEP is simply an ROBP with fractional output values:

For any graph $H$, we use $V(H)$ to denote the vertex set of $H$. As discussed in the introduction, we use the notation $H[x,y]$ to denote the $y$-th neighbor of the vertex $x$ in the graph $H$. This is well-defined provided that $H$ is a labeled graph, defined as follows.

We write $K_R$ to denote the complete graph on $R$ vertices without self-loops, and we write $J_R$ to denote the complete graph on $R$ vertices with self-loops. We write $J$ or $J_{\ast }$ if the number of vertices is clear from context. Several occurrences of “$J_{\ast }$” in a single equation might represent complete graphs on several different numbers of vertices.

If $H$ is a $D$-regular undirected multigraph on $R$ vertices, its transition probability matrix is the matrix $M\in {[0,1]}^{R\times R}$ defined by letting $M_{u,v}=\frac{e(u,v)}{D}$, where $e(u,v)$ denotes the number of edges from $u$ to $v$. We often abuse notation by identifying a graph $H$ with its transition probability matrix. For example, we use $J_R$ to denote the $R\times R$ matrix in which every entry is equal to $1/R$.

For a matrix $M\in {ℝ}^{R\times R}$, we use the notation ${\Vert M\Vert }_{\mathrm{op}}$ to denote the operator norm of $M$, i.e.,

For example, $\lambda (J)=0$. The complete graph without self-loops also has quite a good expansion parameter:

To prove our seed length lower bounds, we rely on the following standard fact.

A proof of Proposition 17 can be found in the full version of this paper [20].

We also use the notation $M\otimes M^{\prime }$ to denote the tensor product of matrices, aka the Kronecker product.

We will use the following weak version of the famous “expander mixing lemma.”

For a proof, see, e.g., Vadhan’s pseudorandomness survey [47].

We now present a more precise definition of the INW generator, in case the informal definition in the introduction was not sufficiently clear.

In this section we briefly review the basic concepts of the coding theory.