Better Pseudorandom Generators from Milder Pseudorandom Restrictions

Introduction

These results, however, remain conditional on a circuit complexity assumption whose proof seems far off at present. Since $\mathsf{PRG}$s that fool a class of Boolean circuits also imply lower bounds for that class, we cannot hope to remove the assumption. Thus unconditional generators are only possible for restricted models of computation for which we have lower bounds.

Bounded-depth circuits and bounded-space algorithms are two models of computations for which we know how to construct $\mathsf{PRG}$s with $O(\log^{O(1)}(n/\varepsilon))$ seed length [Nis91, Nis92]. Known $\mathsf{PRG}$ constructions for these classes have found several striking applications including the design of streaming algorithms [Ind06], algorithmic derandomization [Siv02], randomness extractors [Tre01], hashing [CRSW11], hardness amplification [HVV06], almost $k$-wise independent permutations [KNR05], and cryptographic $\mathsf{PRG}$s [HHR06]. Arguably, constructing $\mathsf{PRG}$s with the optimal $O(\log(n/\varepsilon))$ seed length for these classes are two of the outstanding open problems in derandomization.

Indeed, there are few models of computations for which we know how to construct $\mathsf{PRG}$s with the optimal seed length $O(\log(n/\varepsilon))$ or even $\log^{1+o(1)}(n/\varepsilon)$. The most prominent examples are bounded-degree polynomials over finite fields [NN93, AGHP92, BV10a, Lov08, Vio08], with parities (which are fooled by small-bias distributions [NN93]) as a special case, and models that can be reduced to these cases, such as width-2 branching programs [SZ95, BDVY09].

In summary, there are several interesting models of computation for which a polylogarithmic dependence on $n$ and $1/\varepsilon$ is known, and the dependence on one parameter is logarithmic on its own (e.g. seed length $O(\log n\log(1/\varepsilon))$), but a logarithmic bound in both parameters together has been elusive. Finally, we remark that not having a logarithmic dependence on the error $\varepsilon$ is often a symptom of a more fundamental bottleneck. For instance, $\mathsf{HSG}$s with constant error for width $4$ branching programs imply $\mathsf{HSG}$s with polynomially small error for width $3$ branching programs, so achieving the latter is a natural first step towards the former. A polynomial-time computable $\mathsf{PRG}$ for $\mathsf{CNF}$s with seed length $O(\log n/\varepsilon)$ would imply the existence of a problem in exponential time that requires depth-3 circuits of size $2^{\Omega(n)}$ and that cannot be solved by general circuits of size $O(n)$ and depth $O(\log n)$, which is a long-standing open problem in circuit complexity [Val77].

2 Our Results

$\mathsf{PRG}$s for combinatorial rectangles. Previously, it was known how to construct $\mathsf{HSG}$s with seed length $O(\log(n/\varepsilon))$ [LLSZ97], but the best seed length for $\mathsf{PRG}$s was $O(\log n+\log^{3/2}(1/\varepsilon))$ [Lu02].

$\mathsf{PRG}$s for read-once $\mathsf{CNF}$ and $\mathsf{DNF}$ formulas. Previously, De, Etesami, Trevisan, and Tulsiani [DETT10] and Klivans, Lee and Wan [KLW10] had constructed $\mathsf{PRG}$s with seed length $O(\log n\cdot\log(1/\varepsilon))$.

$\mathsf{HSG}$s for width 3 branching programs. Previously, Sima and Zak [SZ11] had constructed hitting set generators for width 3 branching programs with seed length $O(\log n)$ in case the error parameter $\varepsilon$ is very large (greater than 5/6).

As a corollary of our $\mathsf{PRG}$ for combinatorial rectangles we get improved hardness amplification in NP by combining our results with those of Lu Tsai and Wu [LTW07] - we refer to Section 5 for detailsWe thank an anonymous referee for pointing out this application..

3 Techniques

Our generators are all based on a general new technique — the iterative application of “mild” (pseudo)random restrictions.

We illustrate our technique below with a toy example.

Consider a read-once $\mathsf{CNF}$ formula $f$ of width $w$ with $m=2^{w+1}$ clauses in which the variables appear in order (aka the Tribes function of [BL85]). That is,

where each $f_{i}$ is the OR function. $f$ has constant bias and can be computed both by a combinatorial rectangle and a width-3 branching program. De et al. showed that fooling this function with error $\varepsilon$ using small-bias spaces requires seed-length $\Omega(w\log(1/\varepsilon)/\log\log(1/\varepsilon))$.

Assume we partition the input bits into two parts: $x$ which contains the first $w/2$ variables of each clause and $y$ which contains the rest. Let $x\circ y$ denote the concatenation of the two strings. We would like to show that for ${{\cal D}}$ a small-bias distribution and $\mathcal{U}$ the uniform distribution,

A naive approach might be to view setting $y\sim\mathcal{U}$ as applying a random restriction with probability $1/2$. If this simplified the function $f$ to the extent that it can be fooled by small-bias spaces, we would be done. Unfortunately, this is too much to hope for; it is not hard to see that such a random restriction is very likely to give another Tribes-like function with width $w/2$, which is not much easier to fool using small bias than $f$ itself.

Rather, we need to shift our attention to the bias function of $f$. For each partial assignment $x$, we define the bias function $F(x)$ as

Our key insight is that for restrictions as above, the function $F$ is in fact easy to fool using a small-biased space. This is despite the fact that $F(x)$ is an average of functions $f(x\circ y)$ (by Equation (1.2)), most of which are Tribes-like and hence are not easy to fool.

Let us give some intuition for why this happens. Since $f(x\circ y)=\prod_{i=1}^{m}f_{i}(x\circ y)$,

where $F_{i}(x)$ is the bias function of the $i^{th}$ clause. But note that over a random choice of $y$, $f_{i}(x)$ is set to $1$ with probability $1-2^{-w/2}$ and is a clause of width $w/2$ otherwise. Hence

As a consequence, over a random choice of $x$, we now have

where $S_{k}$ denotes the $k^{th}$ elementary symmetric polynomial and $c_{k}\in$.In the toy example we are currently studying, an alternative and simpler approach is to write $F_{i}(x)=(1-2^{-w/2})^{1-h_{i}(x)}$, where $h_{i}(x)=\vee_{j=1}^{w/2}x_{w(i-1)+j}$ is the indicator for whether $x$ already satisfies the $i$’th clause on its own. Then $F(x)=\prod_{i}F_{i}(x)$ expands as a power series in $\sum_{i}(1-h_{i}(x)-2^{-w/2})$, and higher moment bounds can be used to analyze what happens when we truncate this expansion. However, this expansion is rather specific to the highly symmetric Tribes function, whereas we are able to apply the expansion in terms of symmetric polynomials much more generally.

Under the uniform distribution, one can show that

Towards this end, we prove the following inequality for any real numbers $z_{1},\ldots,z_{m}$:

The proof uses the Newton–Girard formulas (see [CLO07]) which relate the symmetric polynomials and power sums. This lets us repeat the same truncation argument, provided that $S_{1}(g_{1}(x),\ldots,g_{m}(x))$ and $S_{2}(g_{1}(x),\ldots,g_{m}(x))$ are tightly concentrated even under small-bias distributions. We prove this concentration holds via suitable higher moment inequalities.These inequalities actually require higher moment bounds for the $g_{i}$’s. We ignore this issue in this description for clarity, and because we suspect that this requirement should not be necessary.

This lets us show that small bias fools $F(x)$. By iterating this argument $\log w$ times, we get a $\mathsf{PRG}$ for $f$ with polynomially small error and seed-length $O((\log n)(\log w))=O((\log n)(\log\log n))$.

Read-Once 𝖢𝖭𝖥𝖢𝖭𝖥\mathsf{CNF}s.

Combinatorial Rectangles.

A combinatorial rectangle $f:[W]^{m}\rightarrow\{0,1\}$ is a function of the form $f(x_{1},\ldots,x_{m})=\wedge_{i=1}^{m}f_{i}(x_{i})$ for some Boolean functions $f_{1},\ldots,f_{m}$. Thus, here we know which parts of the input correspond to which clauses (like the toy example above), but our clauses are arbitrary functions rather than ORs. To handle this, we use a more powerful family of gradual restrictions. Rather than setting $w/2$ bits of each co-ordinate, we instead (pseudo)randomly restrict the domain of each $x_{i}$ to a set of size $W^{1/2}$. More precisely, we use a small-bias space to pseudorandomly choose hash functions $h_{1},\ldots,h_{m}:[W^{1/2}]\rightarrow[W]$ and replace $f$ with the restricted function $f^{\prime}(z_{1},\ldots,z_{m})=\wedge_{i=1}^{m}(f_{i}\circ h_{i})(z_{i})$.

Width 333 Branching Programs.

For width 3 branching programs, inspired by Sima and Zak [SZ11] we reduce the task of constructing $\mathsf{HSG}$s for width 3 to that of constructing $\mathsf{HSG}$s for read-once $\mathsf{CNF}$ formulas where we also allow some clauses to be parities. Our $\mathsf{PRG}$ construction for read-once $\mathsf{CNF}$s directly extends to also handle such formulas with parities (intuitively because small-bias spaces treat parities just like individual variables). The first step of our reduction actually works for any width $d$, and shows how to reduce the the task of constructing $\mathsf{HSG}$s for width $d$ to constructing hitting set generators for width $d$ branching programs with sudden death, where the states in the bottom level are all assumed to be Reject states.

Organization.

Section 5 describes our $\mathsf{PRG}$ construction for combinatorial rectangles. The reduction from hitting sets for width $3$ branching programs to hitting sets for $\mathsf{CNF}$s with parity is in Section 6. The generator for read-once $\mathsf{CNF}$s and for $\mathsf{CNF}$s with parity are presented in Section 7 and Section 8 respectively.

Preliminaries

We shall make extensive use of small-bias spaces, introduced in the seminal work of Naor and Naor [NN93]. Usually these are defined as distributions over $\{0,1\}^{n}$, but it is more convenient for us to work with $\{\pm 1\}^{n}$.

There exist explicit constructions of $\varepsilon$-biased spaces which can be sampled from with $O(\log n+\log(1/\varepsilon))$ random bits [NN93]. These give efficient pseudorandom generators for the class of parity functions.

Let $0<\alpha,\delta<1/2$. We say a distribution on ${\cal D}$ on $2^{[n]}$ is $\delta$-almost independent with bias $\alpha$ if $I\leftarrow{\cal D}$ satisfies the following conditions:

For any distinct indices $i_{1},\ldots,i_{k}\in[n]$ and $b_{1},\ldots,b_{k}\in\{0,1\}^{k}$,

There exist explicit constructions of distributions in ${\cal D}$ as above which only need $O(\log n+\log(1/\alpha\delta))$ random bits [NN93]. We will write $I\leftarrow{\cal D}(\alpha,\delta)$ for short whenever $I$ is sampled from a $\delta$-almost independent distribution with bias $\alpha$ as above.

Sandwiching Approximators.

It is easy to see that the existence of such approximations implies that $f$ is $\delta+t\varepsilon$ fooled by any $\varepsilon$-biased distribution. In fact, as was implicit in the work of Bazzi [Baz09] and formalized in the work of De et. al. [DETT10], being fooled by small-bias spaces is essentially equivalent to the existence of good sandwiching approximators.

Pseudorandom Generators for 𝖢𝖭𝖥𝖢𝖭𝖥\mathsf{CNF}s.

A Conjunctive normal form formula ($\mathsf{CNF}$) is a conjunction of disjunctions of literals. Throughout we view $\mathsf{CNF}$s as functions on $\{\pm 1\}^{n}$, where we identify $-1$ with $\mathtt{false}$ and $1$ with $\mathtt{true}$. We say a $\mathsf{CNF}$ $f=C_{1}\wedge C_{2}\wedge\cdots\wedge C_{m}$ is a read-once $\mathsf{CNF}$ ($\mathsf{RCNF}$), if no variable appears (by itself or as is its negation) more than once. We call $m$ the size of $f$ and the maximum number of variables in $C_{1},\ldots,C_{m}$ the width of $f$. We shall also use the following results of [DETT10], [KLW10] which say that $\mathsf{RCNF}$s with small number of clauses have very good sandwiching approximators.

Let $f:\{\pm 1\}^{n}\rightarrow\{0,1\}$ be a $\mathsf{RCNF}$ with at most $m$ clauses. Then, for every $\varepsilon>0$, $f$ has $\varepsilon$-sandwiching polynomials with $\operatorname*{\mathsf{L_{1}}}$-norm at most $m^{O(\log(1/\varepsilon))}$.

Let $f:\{\pm 1\}^{n}\rightarrow\{0,1\}$ be a $\mathsf{CNF}$ with at most $m$ clauses and width at most $w$. Then, for every $\varepsilon>0$, $f$ has $\varepsilon$-sandwiching polynomials with $\operatorname*{\mathsf{L_{1}}}$-norm at most $(m/\varepsilon)^{O(w\log w)}$.

Sandwiching Approximators for Symmetric Functions

Our main result on sandwiching approximators for symmetric functions is the following:

Let $\sigma^{2}=(\sum_{i}\sigma_{i}^{2})/m$ and $\delta\in(0,1)$ and $\varepsilon,k>0$ be such that

Let $P(x)=\sum_{i=0}^{m}c_{i}S_{i}(g_{1}(x),\ldots,g_{m}(x))$ be a symmetric multilinear function of the $g_{i}$s that computes a bounded function $P:\{\pm 1\}^{n}\rightarrow[-B,B]$, with $|c_{i}|\leq C$ for all $i\in[m]$. Then,

For every $\varepsilon$-biased distribution $\mathcal{D}$, we have

$P$ has $O(B+C)\delta$ sandwiching approximations of $\operatorname*{\mathsf{L_{1}}}$ norm $O((B+C)(mt+1)^{2k}\delta^{-3})$.

As an illustration of this theorem, we state the following immediate corollary which formalizes the argument for the toy example in the introduction.

To derive Theorem 3.2 from Theorem 3.1, observe that in the notation from Section 1.3, $m=2^{w+1}$, $\sigma^{2}\approx 2^{-3w/2}$ and all the other conditions hold.

In the rest of this section, we prove the first statement of Theorem 3.1. The second statement follows from the first by Lemma 2.6. We first sketch the steps involved in the proof.

Let $k,\varepsilon$ be as in the theorem and let ${\cal D}$ be a $\varepsilon$-biased distribution. Let $P_{\leq k}\equiv\sum_{i=0}^{k}c_{i}S_{i}(g_{1},\ldots,g_{m})$. We will prove the theorem by showing that $P$ cannot distinguish the uniform distribution from ${\cal D}$ by a series of inequalities:

To do this, we first show that there is an event $\mathcal{E}$ that happens with high probability under any $\varepsilon$-biased distribution, and conditioned on which $P_{\leq k}$ is a very good approximation for $P$. We then prove the last inequality by conditioning on the event $\mathcal{E}$ and using Cauchy-Schwarz to bound the error when $\mathcal{E}$ does not occur. The event $\mathcal{E}$ will correspond to $|S_{1}(g_{1},\ldots,g_{m})|$, $|S_{2}(g_{1},\ldots,g_{m})|$ being small, which we show happens with high probability using classical moment bounds. Finally, we show that $P_{\leq k}$ approximates $P$ well if $\mathcal{E}$ happens by using the Newton-Girard Identities for symmetric polynomials (see Lemma 3.6).

Our first task will be to show that under the assumptions of the theorem, $|\sum_{i}g_{i}(x)|$ and $|\sum_{i}g_{i}(x)^{2}|$ are small with high probability. We do so by first bounding the $k$’th moments of these variables and applying Markov’s inequality. For this we will use Rosenthal’s inequalities ([Ros72], [JSZ85], [Pin94]) which state the following:

Let $Z_{i}=g_{i}(x)$, ${x\sim\{\pm 1\}^{n}}$. Then, $Z_{i}$’s are independent mean-zero variables. Now, by Rosenthal’s inequality, Equation (3.2),

The second bound follows similarly by applying Rosenthal’s inequality,Equation (3.3), to the non-negative random variables $Z_{i}^{2}=g_{i}^{2}$:

A consequence of Lemma 3.4 is the following:

For all $k\geq 2$, under any $\varepsilon$-biased distribution $\mathcal{D}$,

Next we show that $|\sum_{i}g_{i}|$, $\sum_{i}g_{i}^{2}$ being small implies the smallness in absolute value of $S_{k}(g_{1},\ldots,g_{m})$ for every $k\geq 2$. Note that there is no probability involved in this statement.

Let $z_{1},\ldots,z_{m}$ be real numbers that satisfy

To prove this lemma, we first bound the power sums $E_{k}(z_{1},\ldots,z_{m})$ which are defined as

Hence we have $|E_{k}(z_{1},\ldots,z_{m})|\leq\mu^{k}$.

The relation between the power sums and elementary symmetric polynomials is given by the Newton-Girard identities (see [CLO07], Chapter 7.1 for instance) discovered in the 17th century.

We use these to show by induction on $k$ that $|S_{k}|\leq\mu^{k}$. For $k=2$, we have

Assume we have proved the bound up to $k-1$. Using the Newton-Girard formula,

denote the truncation of $P$ to degree $k$. We use the following bounds for $P_{\leq k}$.

We observe that the symmetric polynomials $S_{0}=1,\ldots,S_{k}$ on $g_{1},\ldots,g_{m}$ are mutually orthogonal under the uniform distribution, i.e., for $i\neq j$,

For brevity, we shall omit writing out the argument $x$ in the following. For $i\geq 1$, we have

Therefore, assuming that $m\sigma^{2}\leq 1/2$,

Since $\operatorname*{\mathsf{L_{1}}}[g_{j}]\leq t$, we have

which guarantees $\delta^{5}/2\leq(m\sigma^{2})^{k}\leq\delta^{5}$. By Equation (3.1) we have

Finally, for all $\varepsilon$ small enough so that $\varepsilon\cdot(mt+1)^{2k}\leq\delta^{4}$, the following bounds will hold under the assumptions of Theorem 3.1, by Corollary 3.5 and Lemma 3.7,

We now proceed to prove Statement (1) in Theorem 3.1, which we restate below with specific constants.

With the notation from Theorem 3.1, we have

We will show that under any $\varepsilon$-biased distribution $\mathcal{D}$,

Note that $\mathcal{U}$ is $\varepsilon$-biased for $\varepsilon=0$, so the above bound applies to it. We derive Equation (3.16) from Equation (3.17) as follows:

The first and last terms are bounded using Equation (3.17). We bound the middle term by

Equation (3.16) follows by plugging these bounds into Equation (3.18):

We now prove Equation (3.17). Define a good event $G\subseteq\{\pm 1\}^{n}$ containing those $x$ for which the following bounds hold:

We now bound the probability of $\neg G$ using Markov’s inequality applied to a $k$’th moment bound obtained from Equations (3.14) and (3.15):

Let $\mathbf{1}_{G}(x)$ and $\mathbf{1}_{\neg G}(x)$ denote the indicators of $G$ and $\neg G$ respectively. We have

Plugging Equations (3.23) and (3.1) into Equation (3.22) we get Equation (3.17). ∎

An XOR Lemma for ε𝜀\varepsilon-biased spaces

Let $f^{1},\ldots,f^{k}:\{\pm 1\}^{n}\rightarrow$ be functions on disjoint input variables such that each $f^{i}$ has $\varepsilon$-sandwiching approximations of $\operatorname*{\mathsf{L_{1}}}$ norm $t$. Let $H:^{k}\rightarrow$ be a multilinear function in its inputs. Let $h:\{\pm 1\}^{n}\rightarrow$ be defined as $h(x)=H(f^{1}(x),\ldots,f^{k}(x))$. Then $h$ has $(16^{k}\varepsilon)$-sandwiching approximations of $\operatorname*{\mathsf{L_{1}}}$ norm $4^{k}(t+1)^{k}$.

We will show using a hybrid argument, that

For simplicity, we only do the case $S=[k]$. We define a sequence of polynomials $M^{S}_{u}=M_{0},M_{1}\ldots,M_{k}=M^{S}$ where

To construct a lower-sandwiching approximator, we observe that

Finally, let $\mathbf{1}_{S}\in\{0,1\}^{k}$ denote the indicator vector of the set $S$. Since $H$ is multilinear, we can write

A 𝖯𝖱𝖦𝖯𝖱𝖦\mathsf{PRG} for Combinatorial Rectangles

We start by defining combinatorial rectangles ($\mathsf{CR}$s).

A combinatorial rectangle is a function $f:\left(\{\pm 1\}^{w}\right)^{m}\rightarrow\{0,1\}$ of the form $f(x_{1},\ldots,x_{m})=\bigwedge_{i=1}^{m}f_{i}(x_{i})$, where $f_{i}:\{\pm 1\}^{w}\rightarrow\{0,1\}$, and each $x_{i}\in\{\pm 1\}^{w}$.We refer to the $f_{i}$s as the co-ordinate functions of $f$. We refer to $m$ as the sizeThis is usually referred to as the dimension in the literature; we use this terminology for the $\mathsf{CNF}$ analogy. of $f$ and $w$ as the width.

There is an explicit pseudorandom generator for the class of combinatorial rectangles of width $w$ and size $m$ with error at most $\delta$ and seed-length $O((\log w)(\log(m)+w+\log(1/\delta))+\log(1/\delta)\log\log(1/\delta)\log\log\log(1/\delta))$.

Consider the following two-step process for generating a uniformly element $x$ from $\left(\{\pm 1\}^{w}\right)^{m}$.

Choose a sequence of multi-sets $S_{1},\ldots,S_{m}\subseteq\{\pm 1\}^{w}$ each of size $2^{v}$ by picking $2^{v}$ elements of $\{\pm 1\}^{w}$ independently and uniformly at random.

Sample $x_{i}\sim S_{i}$ and set $x=(x_{1},\ldots,x_{m})$.

Our final generator is obtained by iterating the one-step procedure for $T=O(\log\log m))$ steps: At step $t$ we choose multi-sets $S_{1}^{t}\subseteq S_{1}^{t-1},\ldots,S_{m}^{t}\subseteq S_{m}^{t-1}$ each of cardinality exactly $2^{(3/4)^{t}w}$ using small-bias. After $T$ steps, we are left with a rectangle of width $w=O(\log\log m)$. Such rectangles can be fooled by $\varepsilon$-bias spaces where $\varepsilon=1/m^{O(\log\log m)}$. The total randomness used over all the steps is $O((\log m)\cdot(\log\log m))$.

In the following, let $f$ be a $\mathsf{CR}$ of width $w$ and coordinate functions $f_{1},\ldots,f_{m}:\{\pm 1\}^{w}\rightarrow\{0,1\}$. We describe a restriction of $f$ which reduces the width from $w$ to $v=3w/4$.

For every $a\in\{\pm 1\}^{v}$, we sample string $x_{a}=(x_{a,1},\ldots,x_{a,m})\sim\{\{\pm 1\}^{w}\}^{m}$.

For $i\in[m]$, we define restricted co-ordinate functions $f^{v}_{i}$ on inputs $y_{i}$ by $f^{v}_{i}(y_{i})=f(x_{y_{i},i})$.

Define the restricted rectangle $f^{v}:\left(\{\pm 1\}^{v}\right)^{m}\rightarrow\{0,1\}$ on $y_{1},\ldots,y_{m}$ by

Note that each $\bar{f}_{i}$ only depends on column $i$ of $\bar{x}$. Define the bias function of $\bar{x}$ as

The main lemma of this section shows that this bias function can be fooled by small-bias spaces.

For the sample average functions $\bar{f}_{i}$ defined as in Equation (5.2), we have

where the last inequality holds for any Boolean function on $w$ input bits. The bound on the expectation follows directly from Equation (5.2). ∎

The justification for the name bias function comes from the following lemma.

For $f^{v}$ and $F$ as defined in Equation (5.1) and Equation (5.3),

We will need the following technical lemma, which helps us show that the functions $g_{i}$ satisfy the moment conditions needed to apply Theorem 3.1. For brevity, let $\mathcal{U}$ denote $\left(\{\pm 1\}^{v}\right)^{2^{v}\times m}$ in the remainder of this section.

W start by bounding the moments of $(\bar{f}_{i}(\bar{x})-p_{i})$. We have

which is the sum of $2^{v}$ i.i.d $p_{i}$-biased random variables with mean . Hence we can apply Rosenthal’s inequality (Equation (3.2)) to get

For $j\in$, let $F_{j}(\bar{x})=\prod_{i\in S_{j}}\bar{f}_{i}(\bar{x})$ so that $F(\bar{x})=\prod_{j=1}^{3}F_{j}(\bar{x})$. We will construct sandwiching approximations for each $F_{j}$ and then combine them via Theorem 4.1. We assume without loss of generality that $p_{i}\leq 1-2^{-w}$. Else, the $i$’th coordinate has bias $1$ and can be ignored without changing the rest of the proof.

We show that $\operatorname*{\mathsf{L_{1}}}[F_{1}]$ is itself small. Observe that $\delta\leq p=\prod_{i=1}^{m}p_{i}\leq\prod_{i\in S_{1}}p_{i}\leq 2^{-v|S_{1}|/10}$, which implies that $|S_{1}|\leq 10\log(1/\delta)/v$. Thus, by Claim 5.4,

Hence Theorem 3.1 implies the existence of $O(\delta)$ ($B=1$ and $C=\prod_{i\in S_{2}}p_{i}\leq 1$) sandwiching approximations with $\operatorname*{\mathsf{L_{1}}}$ norm bounded by $(mt+1)^{2k}$ where

By Theorem 3.1, $F_{3}$ has $O(\delta)$ sandwiching approximations with $\operatorname*{\mathsf{L_{1}}}$ norm bounded by $(mt+1)^{2k}$ where

Sandwiching F𝐹F.

The last inequality holds since at each step, we at most double the acceptance probability of the chosen co-ordinate, and hence of the overall formula. Hence we have

2 A Recursive Sampler for Combinatorial Rectangles

We now use Lemma 5.3 recursively to prove Theorem 5.2. Our generator is based on a derandomized recursive sampling procedure which we describe below. The inputs are the width $w$ and the size $m$ of the rectangles we wish to fool and an error parameter $\delta\leq 1/2^{w}$.

Let $v_{0}=w$, $v_{j}=\left(\frac{3}{4}\right)^{j}w$.

While $v_{j}\geq 50\log\log(1/\delta)$ we sample $\bar{x}_{j}\in\{\{\pm 1\}^{v_{j-1}}\}^{2^{v_{j}}\times m}$ according to an $\varepsilon_{1}$-biased distribution for $\varepsilon\leq(1/\delta)^{c_{1}}$ for some large constant $c_{1}$.

Assume that at step $t$ (where $t=O(\log w)$), $v_{t}\leq 50\log\log(1/\delta)$. Sample an input $\bar{x}_{t}\in\left(\{\pm 1\}^{v_{t-1}}\right)^{m}$ from an $\varepsilon_{2}$-biased distribution where, for some large constant $c_{2}$,

We next describe how we use $\mathbf{x}=(\bar{x}_{1},\ldots,\bar{x}_{t})$ to output an element of $\left(\{\pm 1\}^{w}\right)^{m}$. For $k\in\{1,\ldots,t-1\}$ we denote by $s_{k}$ the recursive sampling function which takes strings $\bar{x}_{j}\in\{\{\pm 1\}^{v_{j-1}}\}^{2^{v_{j}}\times m}$ for $j\in\{k+1,\ldots,t-1\}$ and $\bar{x}_{t}\in\left(\{\pm 1\}^{v_{t}}\right)^{m}$ and produces an output string $s_{k}(\bar{x}_{k+1},\ldots,\bar{x}_{t})\in\left(\{\pm 1\}^{v_{k}}\right)^{m}$. Set $s_{t-1}(\bar{x}_{t})\equiv\bar{x}_{t}$. Fix $k<t-1$ and let $z=s_{k+1}(\bar{x}_{k+2},\ldots,\bar{x}_{t})$ be already defined. To define $s_{k}$, we will use $z$ to look up entries from the matrix $\bar{x}_{k+1}$, so that the $i$’th coordinate of $s_{k}$ will be the entry of $\bar{x}_{k+1}$ in the $z_{i}$’th row and $i$’th column:

The above definition, though intuitive is a bit cumbersome to work with. It will be far easier for analysis to fix the input combinatorial rectangle $f:\left(\{\pm 1\}^{w}\right)^{m}\rightarrow\{0,1\}$ and study the effect of the samplers $s_{k}$ on $f$. Let $f^{0}=f$. Each matrix $\bar{x}_{j}$ gives a restriction of $f^{j-1}$: it defines restricted co-ordinate functions $f_{i}^{j}:\{\pm 1\}^{v_{j}}\rightarrow\{0,1\}$ and a corresponding restricted rectangle $f^{j}:\{\{\pm 1\}^{v_{j}}\}^{m}\rightarrow\{0,1\}$. We only use the following property of the $s_{j}$s:

To analyze the last step, we use the following corollary that follows from [DETT10].

Every combinatorial rectangle $f:\{\{\pm 1\}^{v}\}^{m}\rightarrow\{\pm 1\}$ is $\delta$-fooled by $\varepsilon$-bias spaces for $\varepsilon=\left(m2^{v}/\delta\right)^{-O(v\log v)}$.

Each co-ordinate function $f_{i}$ can be expressed as a $\mathsf{CNF}$ formula with $2^{v}$ clauses of width $v$. Hence we can write $f$ as a $\mathsf{CNF}$ formula with $m2^{v}$ clauses of width $v$. Now apply Theorem 2.8. ∎

be the domain of $\mathbf{x}$ as defined in the generator construction.

Let ${{\cal D}}^{j}$ denote the distribution on $\mathcal{U}$ where $\bar{x}_{i}$ are sampled from an $\varepsilon$-biased distribution for $i<j$ and uniformly for $i\geq j$. Then, $s_{0}({{\cal D}}^{0})$ is the uniform distribution on $\{\{\pm 1\}^{w}\}^{m}$ whereas $s_{0}({{\cal D}}^{t})$ is the output of our Recursive Sampler.

Let $f:\{\{\pm 1\}^{w}\}^{m}\rightarrow\{0,1\}$ be a combinatorial rectangle with width $w$ and size $m$. For distributions ${{\cal D}}^{0}$ and ${{\cal D}}^{t}$ defined above, we have

Let $\delta^{\prime}=\delta/t$. We will show by a hybrid argument that for all $j\in\{1,\ldots,t\}$

In both ${{\cal D}}^{j-1}$ and ${{\cal D}}^{j}$, $\bar{x}_{i}$ is drawn from an $\varepsilon$-biased distribution for $i<j$, and from the uniform distribution for $i>j$. The only difference is $\bar{x}_{j}$ which is sampled uniformly in ${{\cal D}}^{j-1}$ and from an $\varepsilon$-biased distribution in ${{\cal D}}^{j}$.

We couple the two distributions by drawing $\bar{x}_{i}$ for $i<j$ according to an $\varepsilon$-biased distribution. By Equation (5.4), we get

Define the bias function $F^{j-1}$ of the rectangle $f^{j-1}$ as in Equation (5.3). The string $\bar{x}_{j}$ defines a restricted rectangle $f^{j}:\{\{\pm 1\}^{v_{j}}\}^{m}\rightarrow\{0,1\}$. Applying Claim 5.5 we get

In both distributions ${{\cal D}}^{j-1}$ and ${{\cal D}}^{j}$, $\bar{x}_{j+1},\ldots,\bar{x}_{t}$ are distributed uniformly at random, hence $s_{j}({{\cal D}}^{j-1})=s_{j}({{\cal D}}^{j})\sim\left(\{\pm 1\}^{v_{j}}\right)^{m}$ are uniformly distributed, and this variable is independent of $\bar{x}_{j}$. So we have

For $j=t$, note that this is equivalent to showing that $\varepsilon_{2}$-bias fools the rectangle $f^{t}$. By Corollary 5.7, $f^{t}$ is $\delta^{\prime}$ fooled by $\varepsilon_{2}$-biased spaces where

Plugging these back into Equation (5.5), the error is bounded by $t\cdot\delta^{\prime}\leq\delta$. ∎

To complete the proof of Theorem 5.2, we observe that the total seed-length is

𝖧𝖲𝖦𝖧𝖲𝖦\mathsf{HSG}s for Read-Once Branching Programs

In thsi section, we reduce the problem of constructing an $\mathsf{HSG}$ for width $3$ branching programs to the problem of $\mathsf{HSG}$ construction for $\mathsf{CNF}$ formulas which are allowed to have parity functions as clauses. We start with some definitions.

A read-once branching program (ROBP) $B$ of width $d$ has a vertex set $V$ partitioned into $n+1$ layers $V_{0}\cup\cdots\cup V_{n}$ where

$V_{t}=\{(t,i)\}_{i\in[d]}$ for $t\in\{1,\ldots,n-1\}$.

The vertex $(0,0)$ is referred to as the Start state, while $(n,1)$ and $(n,d)$ are referred to as Acc and Rej, respectively. Each vertex in $v\in V_{t}$ has two out-edges labeled and $1$, which lead to vertices $N_{0}(v)$ and $N_{1}(v)$ respectively in $V_{t+1}$. We refer to the set of states $\{(t,1)\}_{t=1}^{n}$ as the top level and $\{(t,d)\}_{t=1}^{n}$ as the bottom level.

Let $\mathsf{BP(d,n)}$ denote the set of all $f:\{0,1\}^{n}\rightarrow\{0,1\}$ that can be computed by width $d$ ROBPs. Our hitting set generator for $\mathsf{BP(3,n)}$ uses a reduction to the problem of hitting $\mathsf{CNF}$ formulas where clauses can be disjunctions of variables or parity functions.

Let $\mathsf{CNF^{\oplus}}(n)$ denote the class of read once formulas $f:\{0,1\}^{n}\rightarrow\{0,1\}$ of the form $f=\wedge_{i=1}^{m}T_{i}$ where each $T_{i}$ is either a disjunction of literals or a parity function of literals and the $T_{i}$s are on disjoint variables.

Given this reduction, we get a $\mathsf{HSG}$ for $\mathsf{BP(3,n)}$ by using the $\mathsf{PRG}$ for $\mathsf{CNF^{\oplus}}$ that we construct in Theorem 8.2:

For every $\varepsilon>0$, there exists an explicit $(\varepsilon,(\varepsilon/n)^{O(1)})$-$\mathsf{HSG}$ $G:\{0,1\}^{r}\rightarrow\{0,1\}^{n}$ for $\mathsf{BP(3,n)}$ with a seed-length of $O((\log(n/\varepsilon))\cdot(\log\log(n/\varepsilon))^{3})$.

We remark that using similar techniques, we can also achieve a seed-length of $O((\log n)(\log(1/\varepsilon)))$ which is better than the above bound for large values of $\varepsilon$. We defer the details of this to the full version.

The reduction in Theorem 6.2 is carried out in three steps.

The first step (for the sake of $\mathsf{HSG}$s) reduces arbitrary width $3$ programs to “sudden death” width $3$ programs, where the last state in every layer is a Rej state. (This step in fact works for all widths.)

The second step reduces “sudden death” width $3$ programs to intersections of width $2$ programs.

The third step reduces intersections of width $2$ programs to $\mathsf{CNF^{\oplus}}$ formulae.

A width $d$ BP with sudden death is a BP where the bottom level states are all ${\sf Rej}$ states. Formally this means $N_{0}((t,d))=N_{1}((t,d))=(t+1,d)$ for all $t=1,\ldots,n-1$. Let $\mathsf{BP^{Rej}(d,n)}$ denote the set of functions computable by such programs.

We reduce the problem of constructing hitting sets for width $d$ BPs to for ones with sudden death.

We first setup some notation. For a vertex $v\in V$ let $p(v)$ denote the probability of reaching Acc starting from $v$ over a uniformly random choice of $x_{i+1},\ldots,x_{n}$. We call a state $v\in V$ such that $p(v)=0$ a Rej state. We order states in $V_{t}$ so that

Observe that, if $v\in V_{j}$ is such that $p(v)\leq\mu$, then $p((i,d))\leq\mu$ for all $i\geq j$.

Let $B\in\mathsf{BP(d,n)}$. Let $R$ be a set of states such that $p(v)\leq\mu\ \forall v\in R$ and let $j$ be the first layer such that $R\cap V_{j}\neq\emptyset$. Let $B^{\prime}$ be obtained from $B$ by converting all states in $R$ into Rej states by redirecting the edges out of $v\in R\cap V_{i}$, $i\geq j$, to $((i+1,d))$. Let $p^{\prime}(v)$ denote the accepting probabilities of vertices in $B^{\prime}$. Then for all $v\in V$, we have $p^{\prime}(v)\geq p(v)-\mu$.

If $p(v)\leq\mu$ the claim is trivial, so fix $v$ such that $p(v)>\mu$. Let $R(x)$ denote the event that we visit a vertex in $R$ if we follow $x$ from $v$ in $B$ and let $u(x)$ denote the first vertex in $R$ that is visited by this path. Let ${\sf Acc}(x)$ denote the event that $B$ accepts. We have

where we use $\Pr_{x}[{\sf Acc}(x)|u(x)=r]=p(r)\leq\mu$ for all $r\in R$. But then

Finally, note that if we accept $x$ without ever reaching $R$ in $B$, then $x$ is also accepted by $B^{\prime}$. Hence $p^{\prime}(v)\geq p(v)-\mu$. ∎

Thus, a random walk starting at $v$ reaches the top level with probability at least $\varepsilon/2$ (since this is a necessary condition for $B^{\prime}$ to accept). For $j\in\{i,\ldots,n-1\}$, let $q(j)$ denote the probability that we reach the top level for the first time at layer $j$. So

Hence there exists $j$ so that $q(j)\geq\varepsilon/2n$.

We now make the following modifications to $B^{\prime}$ to get a program $B^{\prime\prime}$ which is a width $d$ program with sudden death:

For $t\in\{i,\ldots,j-1\}$ we convert the states $(t,1)$ into Rej states.

For $t\in\{j,\ldots,n+1\}$ we convert the states $(t,d)$ into Rej states.

We don’t need to add an additional layer for making these modifications since we are turning one state in each layer to a Rej state.

It is clear that $B^{\prime\prime}$ computes a function $f^{\prime\prime}\leq f^{\prime}$. Our goal is to show that $B^{\prime\prime}$ accepts a large subset of inputs accepted by $B^{\prime}$. Indeed, we claim that

We observe that the probability that a random walk starting at $v$ reaches the top level for the first time in layer $j$ is the same in $B^{\prime\prime}$ as in $B^{\prime}$, hence it equals $q(j)\geq\varepsilon/2n$. Further, using Lemma 6.6 (to the sub-program of $B^{\prime}$ starting at $(j,1)$) we claim that

where we use the fact that $p^{\prime}(j,1)=p(j,1)\geq p(1,1)\geq\varepsilon$. Note that the probability that $B^{\prime\prime}$ accepts is at least $q(j)p^{\prime\prime}(j,1)\geq\varepsilon^{2}/4n$, which comes from strings which reach state $(j,1)$ and then reach Acc.

The theorem now follows by setting $g\equiv f^{\prime\prime}$. By definition, $f^{\prime\prime}\in\mathsf{BP^{Rej}(d,n-k)}$ and

We now reduce width $3$ programs with sudden death to intersections of width $2$ programs.

Throughout this section, we are given $B\in\mathsf{BP^{Rej}(d,n)}$ computing $f:\{0,1\}^{n}\rightarrow\{0,1\}$. Let ${\sf Bad}$ denote the set of non-reject states that have an out-edge leading to a ${\sf Rej}$ state (which are all states such that $p(v)=0$). Further for each $x\in\{0,1\}^{n}$, let ${\sf Bad}(x)$ denote the number of ${\sf Bad}$ states visited by $x$.

Suppose that $t\geq 1$. For $i\in[n]$, let $Y_{i}$ denote the number of vertices in ${\sf Bad}$ visited by $\mathsf{Path}(x)$ in the first $i$ layers. Then, $Y_{n}={\sf Bad}(x)$. We claim that,

This is because, if $\mathsf{Path}_{i}(x)\in{\sf Bad}$, then with probability at least $1/2$, $\mathsf{Path}_{i+1}(x)$ is a Rej state, in which case $\mathsf{Path}_{j}(x)$ is a Rej state for every $j\geq i+1$.

Further, if $Y_{n}\geq t$, then there must be an index $i<n$, where $Y_{i}\geq t-1$, $\mathsf{Path}_{i}(x)\in{\sf Bad}$ and $Y_{n}>Y_{i}$ (for instance $i$ can be the least $j$ such that $Y_{j}=t-1$). Therefore,

where the last two inequalities follow from Equation (6.1) and the fact that $Y_{i}$’s are non-decreasing. The claim now follows by induction. ∎

Let $\Pr_{x\sim\{0,1\}^{n}}[f(x)=1]=p$. Then

The rest of our argument is specific to $d=3$. We restrict our attention to the accepting strings $x\in f^{-1}(1)$. For each vertex $v\in V$ let $q(v)=\Pr_{x\sim f^{-1}(1)}[v\in\mathsf{Path}(x)]$. Each layer $t$ has three states $(t,1),(t,2)$ and $(t,3)\in{\sf Rej}$. We assume that $q((t,1))\geq q((t,2))\geq q(t,3)=0$ (since accepting strings never visit a ${\sf Rej}$ state). We first bound the probability mass on states in the set ${\sf Bad}$.