Simplifying Armoni’s PRG

In this paper we revisit the problem of constructing pseudo-random generators ($\mathrm{𝖯𝖱𝖦}$s) against bounded width read-once branching programs ($\mathrm{𝖱𝖮𝖡𝖯}$s).¹¹1For a formal definition of $\mathrm{𝖱𝖮𝖡𝖯}$and $\mathrm{𝖯𝖱𝖦}$ see Definitions 1 and 2. Nisan [9] constructed a $\mathrm{𝖯𝖱𝖦}$ $\epsilon$–fooling length $t$ width $w$ $\mathrm{𝖱𝖮𝖡𝖯}$ over $\mathrm{\Sigma }$ with seed length $\mathrm{\Theta }(\log t\cdot \log \frac{wt|\mathrm{\Sigma }|}{\epsilon })$ using pair-wise independence. Impagliazzo, Nisan and Wigderson [7] gave a variant of the construction with a similar seed length, but using expanders, extractors or samplers instead of pair-wise independence. The INW $\mathrm{𝖯𝖱𝖦}$ has seed length $\log |\mathrm{\Sigma }|+\mathrm{\Theta }(\log t\cdot \log \frac{wt}{\epsilon })$.

For the special case when the width $w$ of the $\mathrm{𝖱𝖮𝖡𝖯}$ is much larger then the length of the $\mathrm{𝖱𝖮𝖡𝖯}$ and the error, i.e., $t\le {\log }^{c}w,\epsilon \ge 2^{-{\log }^{0.9}w}$ for some constant c, Nisan and Zuckerman [10] constructed a different $\mathrm{𝖯𝖱𝖦}$ with an optimal seed length $\mathrm{\Theta }(\log \frac{wt}{\epsilon })$. Armoni [1] recursively used the NZ construction, and with a careful analysis obtained a $\mathrm{𝖯𝖱𝖦}$ with seed length $\mathrm{\Theta }(\log t\cdot \frac{\log \frac{wt}{\epsilon }}{\max \{\log \frac{\log w}{\log \frac{t}{\epsilon }},1\}})$ for constant size $\mathrm{\Sigma }$ where $t\le 2^{{\log }^{1-\epsilon }w}$ for some constant $\epsilon >0$.

In [8] Armoni’s PRG is instantiated with a specific space-explicit extractor removing the parameters limit, and the resulting seed length is $2\log |\mathrm{\Sigma }|+\theta (\log t\cdot \frac{\log \frac{wt}{\epsilon }}{\max \{\log \frac{\log w}{\log \frac{t}{\epsilon }},1\}})$. Armoni’s $\mathrm{𝖯𝖱𝖦}$ with [8] bridges the gap between INW and NZ - it asymptotically matches INW when $t/\epsilon$ is large, and it matches NZ when $t/\epsilon$ is small compared to $w$.

In this paper we construct another $\mathrm{𝖯𝖱𝖦}$ that matches the parameters obtained in Armoni. The surprising thing about our construction is that it avoids altogether the NZ $\mathrm{𝖯𝖱𝖦}$, and also avoids the recursion in Armoni, and instead it is a direct, simple variant of INW. Saying it differently, Armoni interpolates between two different $\mathrm{𝖯𝖱𝖦}$ constructions: the NZ $\mathrm{𝖯𝖱𝖦}$ and the INW $\mathrm{𝖯𝖱𝖦}$, and his construction is a recursive combination of both. Instead, we show that a simple variant of INW alone gives the same bounds for all parameter regimes.

To understand our new construction, we revisit the INW construction. The main building block behind the INW construction is showing that one can recycle the randomness given to a $\mathrm{𝖯𝖱𝖦}$, where the recycling is done using an expander, or more generally, a sampler or an extractor. Specifically, instead of applying twice a $\mathrm{𝖯𝖱𝖦}$ with two independent seeds, one can apply it once (consuming $s$ random bits) and then use a short seed (of length $d\ll s$) to recycle the $s$ bits and get from it a new seed for the second application of the $\mathrm{𝖯𝖱𝖦}$. The constructions in [9, 7] preserve the same seed lengths for the two applications of the $\mathrm{𝖯𝖱𝖦}$s (we say, in short, that INW preserves the block length).

Nisan and Zuckerman observe that the seed needed for the extractor has length $d=O(\log \frac{t}{\epsilon })$ while the string it acts upon has length $s=\mathrm{\Omega }(\log w)$, and so when $t/\epsilon \ll w$, instead of applying the extractor once, it is more beneficial to apply it $u=O(\frac{\log w}{\log t/\epsilon })$ times with independent seeds of length $d$. Extending these ideas, Armoni implements this idea recursively.

In this paper we suggest an alternative to NZ and Armoni where instead of taking a large $u$ so that $ud=s$, we keep $u=1$ and instead track down our losses. Next, we explain this idea in detail.

Suppose we start with a seed $y$ of length $s$ and we want to create from it two seeds for two independent applications of the $\mathrm{𝖯𝖱𝖦}$. The way INW achieves this is by carving out $d$ bits from $y$ and reserving them for the extractor application. Specifically, say $y=y_{left}\circ y_{right}$ where $y_{right}$ has length $d$. Then, in INW, the first $\mathrm{𝖯𝖱𝖦}$ is called with the seed $y_{left}$, and the second $\mathrm{𝖯𝖱𝖦}$ is called with the seed $Ext(y_{left},y_{right})$, where $Ext$ is an extractor. Thus, the seed length for the first application is $s-d$ and the seed length for the second application is the extractor output size, and it suffers the losses the extractor suffers. These include:

• $\mathrm{■}$

  The amount of information the machine knows about $y_{left}$ after seeing the output of the first $\mathrm{𝖯𝖱𝖦}$. This loss amounts to $\mathrm{\ell }=O(\log \frac{tw}{\epsilon })$.

• $\mathrm{■}$

  The extractor entropy loss, which is $2\log 1/\epsilon$ in non-explicit constructions. For the time being let us assume we can achieve a $O(\mathrm{\ell })$ loss explicitly, and then this loss is comparable with the first loss.

Thus, the seed loss in the first $\mathrm{𝖯𝖱𝖦}$ application is $d=O(\log \frac{t}{\epsilon })$, whereas the loss in the second $\mathrm{𝖯𝖱𝖦}$ application is larger and is $O(\log \frac{tw}{\epsilon })$. The two losses are quite different when $t/\epsilon \ll w$.

We then do the obvious. We define a recursive construction, where starting with a seed length $s$ we get two recursive calls, one with seed length $s-d$ and one with seed length $s-\mathrm{\ell }$, where $d=O(\log \frac{t}{\epsilon })$ and $\mathrm{\ell }=O(\log \frac{wt}{\epsilon })$. Doing the analysis we find out that we recover the bound $\log |\mathrm{\Sigma }|+\mathrm{\Theta }(\log t\cdot \frac{\mathrm{\ell }}{\log (\frac{\mathrm{\ell }}{d}+1)})$ in a much simpler way.

To summarize, when $t/\epsilon \ll w$, it is much better to employ the INW strategy with varying block lengths, and doing so gives the correct parameters in a straight forward way. However, NZ and later Armoni try to preserve the block length throughout different calls. This forces NZ to use several calls of the extractor, and later forces Armoni to use specially crafted recursion (and a more careful analysis). What we show here is that all of that is unnecessary, and with varying block lengths the INW construction obtains the same parameters as NZ and Armoni.

For our construction to work, we require space-efficient extractors with small entropy loss. In general, there are non-explicit $(k,ϵ)$ extractors $E:{\{0,1\}}^n\times {\{0,1\}}^d\to {\{0,1\}}^m$ with entropy loss $2\log 1/\epsilon +O(1)$, i.e., $m=k+d-2\log 1/\epsilon -O(1)$, and notice that the entropy loss is independent of $k$. Kane et al. in [8] instantiated Armoni’s $\mathrm{𝖯𝖱𝖦}$ with the GUV extractor [6, Theorem 5.10] which has $\mathrm{\Omega }(k)$ entropy-loss, and they show it is space-efficient. However, $\mathrm{\Omega }(k)$ loss is too much for us.

In general, the best explicit extractors have $\mathrm{\Omega }(\frac{k}{poly(\log k))})$ entropy-loss [5, 11]. What saves us here is that we do not need general extractors but rather extractors working in the very-high min-entropy regime, where $\mathrm{\Delta }=n-k$ is small. In this regieme one can split the source to a large block followed by a second small block of length $O(\mathrm{\Delta })$, and then use a block-wise extractor. This was implemented in [2]. The resulting extractor is cited in Theorem 4, has low entropy-loss and is space-efficient.

Replacing the lossy extractor used in [8] with the small entropy-loss extractor of [2] has other benefits. It turns out this also reduces the additive dependence on $|\mathrm{\Sigma }|$ from $2\log |\mathrm{\Sigma }|$ to $\log |\mathrm{\Sigma }|$. We summarize the parameters obtained by the previous constructions and by our construction in Table 1.

We remark that while the improvement in the dependence of $\mathrm{\Sigma }$ may seem insignificant, it can help simplify certain constructions. A notable example is the recent work of Cheng and Wu [3] which employs an iterative process of alternating steps of length and alphabet reductions. Using our $\mathrm{𝖯𝖱𝖦}$ (and [2] extractor) in the length reduction, the alphabet reduction becomes unnecessary.

$[k]$ denotes the set $\{1,\mathrm{\dots },k\}$. For a $k\times k$ matrix M and $i,j\in [k]$, $M[i,j]$ is the value of M at the $i$’th row and $j$’th column. $\Vert M\Vert$ is the spectral norm of $M$. For every $f:[w]\to [w]$ there is a corresponding $w\times w$ boolean matrix $M_f$ such that $M_f[i,j]=1$ iff $f(j)=i$. We denote the set of such matrices by $SB{M}_{w\times w}$ (stochastic, boolean matrices).

As explained in the introduction, we apply the INW approach, each time replacing a seed with two different (shorter) seeds. Unlike INW the two seeds have different lengths. Specifically, if we start with an initial seed of length $s$, then we can only pass $s-d$ bits to the first application of the $\mathrm{𝖯𝖱𝖦}$, because we need to keep $d$ independent bits for the recycling step. When we recycle the randomness, say with an extractor, and get a new seed for the second $\mathrm{𝖯𝖱𝖦}$, we can recover these $d$ bits but we have two new losses:

• $\mathrm{■}$

  An entropy loss of order $O(\log \frac{1}{{\epsilon }^{\prime }})$, where ${\epsilon }^{\prime }$ is the extractor error, which we take to be $\mathrm{\Theta }(\frac{\epsilon }{t})$, where $\epsilon$ is the final error, and $t$ is the final number of blocks, and,

• $\mathrm{■}$

  A $\log \frac{w}{{\epsilon }^{\prime }}$ loss, that is due because of the information collected in the width $w$ branching program after seeing the output of the first $\mathrm{𝖯𝖱𝖦}$.

Thus, for the second application we lose $\mathrm{\ell }=O(\log \frac{wt}{\epsilon })$ bits. As $d=O(\log \frac{t}{\epsilon })$ it is significantly smaller than $\mathrm{\ell }$ when $w\gg \frac{t}{\epsilon }$. To summarize, we replace a length $s$ seed, with two seeds, one of length $s-d$ and the other of length $s-\mathrm{\ell }$ where $d=O(\log \frac{t}{\epsilon })$ and $\mathrm{\ell }=O(\log \frac{wt}{\epsilon })$, where the constants behind the big O notation are essentially determined by the seed length and the entropy loss of the explicit extractor that we use (plus an additive $\log \frac{w}{{\epsilon }^{\prime }}$ added to $\mathrm{\ell }$).

Having the recycling building block, we use it recursively and define a sequence of $\mathrm{𝖯𝖱𝖦}$s. Applying this idea in a tree-like construction, we have the following construction:

We need to analyze the output length of the generator and to prove correctness. We start by analyzing the output length of $P_s$ as a function of the seed length $s$.