The famous "L vs. BPL" problem asks whether randomness is ever truly necessary for space-efficient computation. To prove L = BPL, it suffices to design a suitable pseudorandom generator (PRG), i.e., an efficient algorithm that stretches a short truly random seed to a long bitstring that "looks random". To be more specific, the action of a small-space algorithm on its random bits can be modeled by a read-once branching program (ROBP). Therefore, to prove L = BPL, it suffices to design an efficient PRG with seed length O(log n) that fools polynomial-width ROBPs.
A large and growing body of work has made significant progress toward this ambitious goal. Most work on L vs. BPL can be broadly divided into two main approaches.
The "classical" approach to L vs. BPL is based on the observation that there is limited communication between the first half of an ROBP and its second half. Therefore, after using a few truly random bits to generate the first half of a pseudorandom string, the truly random bits can be efficiently recycled to generate the second half of the pseudorandom string. This insight is essentially due to Nisan [26].
Of the line of work that uses this approach, some highlights include PRGs for polynomialwidth ROBPs with seed length O(log 2 n) [26,20,15]; PRGs for constant-width "regular" ROBPs with seed length O(log n) [7,11,21,32,6]; and derandomization techniques that go beyond the construction of PRGs [27,31]. More recently, this "seed recycling" approach has been used to obtain improved generators for polynomial-width ROBPs when the error parameter ε is very small [5,19].
The more "modern" approach to L vs. BPL is to design a pseudorandom generator by iterated pseudorandom restrictions. That is, we pseudorandomly assign values to a pseudorandomly chosen subset of the variables, and then repeat the process to assign values to all variables. Intuitively, designing a pseudorandom restriction for some function f is easier than fooling f outright, because designing a pseudorandom restriction amounts to fooling a "smoothed out" version of f [16], or equivalently, designing a PRG that would fool f if some noise were added [18]. This "iterated restrictions" approach goes back to early work by Ajtai and Wigderson [2], but its modern incarnation is largely due to Gopalan et al. [16].
Of the line of work that takes this approach, some highlights include PRGs for arbitrarilyordered ROBPs with seed length polylog n [33,9,14]; PRGs for width-3 ROBPs with seed length O(log n) [16,33,24]; PRGs for bounded-depth read-once formulas with seed length O(log n) [16,10,13]; and near-optimal PRGs for arbitrary-order product tests [18,22].
At two extremes, one can either try to derandomize all of BPL as efficiently as possible (e.g. [26,31]), or else one can try to optimally derandomize as much of BPL as possible (e.g. [28,29]). Let us adopt the second goal.
In some cases, the "seed recycling" approach has indeed yielded PRGs with truly optimal seed length, at least for moderate error. For example, PRGs are known with seed length O(log n) that fool all O(log n)-space algorithms that use only polylog(n) random bits in the first place [1,28,19]. For another example, PRGs for constant-width "permutation" ROBPs are known with seed length O(log n) [11,21,32]. D. Doron, P. Hatami, and W. M. Hoza
The present work considers the question of whether the "iterated restrictions" approach can also yield a PRG with seed length O(log n) for some interesting class of tests. At first glance, this might seem doubtful, since after all we must pay for many pseudorandom restrictions. Nevertheless, we answer in the affirmative, proving the following theorem.
Theorem 1. For all n ∈ N and ε > 0, there is an explicit ε-PRG for read-once depth-2 AC 0 [⊕] formulas on n input bits with seed length
Specifically, the seed length of our PRG is O log n + log(1/ε) • (log log(1/ε)) 5 . One can prove a lower bound of Ω(log n + log(1/ε)) on the seed length of any PRG for this model. 1
The class of functions that is fooled by our PRG (read-once depth-2 formulas over the basis {∧, ∨, ⊕}, with negations allowed at the inputs for free) is certainly of interest. It includes read-once CNFs and read-once F 2 -polynomials as special cases. The problems of fooling these classes have both received a lot of attention [12,16,4,23,24,22]. Previously, even for read-once CNFs, PRGs with seed length O(log n) were only known for constant error [8,12], whereas our PRG maintains seed length O(log n) with near-optimal error ε = exp(-Ω(log n)). Meanwhile, for read-once F 2 -polynomials, no PRGs with seed length O(log n) were known at all prior to our work.
Gopalan et al. did give a PRG with near-optimal seed length O(log(n/ε)) for read-once CNFs, and more generally for read-once depth-2 AC 0 [⊕] formulas with the property that the output gate is not ⊕ [16]. They used their PRG to construct a near-optimal hitting set for width-3 ROBPs [16]. A subsequent line of work provided near-optimal PRGs for all read-once depth-2 AC 0 [⊕] formulas [23,24,22]. 2 Conversely, a read-once depth-2 AC 0 [⊕] formula can be simulated by a width-4 ROBP (after suitably permuting the variables). The problems of designing improved PRGs for width-4 ROBPs and for read-once AC 0 [⊕] formulas of any constant depth are two major frontiers in unconditional pseudorandomness [24,13]. The model we study in this paper is an interesting special case.
Let us focus on the problem of designing a PRG with seed length O(log n), with ε as small as possible. For simplicity, assume the test function is a read-once
Ultimately, we wish to design a full PRG via iterated pseudorandom restrictions. To begin, we will explain how to construct just one pseudorandom restriction that assigns values to a constant fraction of the inputs. We use almost O(log n)-wise independence to select the subset of inputs to keep "alive" for each coordinate, where the probability of staying alive is a constant p ≈ 1. We use a small-bias distribution to assign values to the remaining inputs. Sampling this pseudorandom restriction only costs O(log n) truly random bits.
Building on prior work [30,18,9], Forbes and Kelley showed that a restriction based on δ-biased distributions preserves the expectation of any arbitrary-order constant-width ROBP to within error 1/n, where log(1/δ) = O(log n log log n) [14]. Our test function f can be simulated by a width-4 ROBP under some variable order. Unfortunately, given our budget of O(log n) truly random bits, we can only afford to sample from a (1/ poly(n))-biased distribution.
To move forward, let us turn things around a little: the analysis of Forbes and Kelley shows that a restriction based on δ-biased distributions preserves the expectation to within error ε, where ε = exp(-Ω(log(1/δ)/ log log(1/δ))). The point is that this latter statement holds even for a relatively large δ, assuming the ROBP reads at most 1/ε variables. Therefore, if we assume that our test function f only reads a few variables (say, polylog n many), then the Forbes-Kelley approach shows that our pseudorandom restriction preserves the expectation of f to within error ε = exp(-Ω(log n/ log log n)).
Assume this time that the degree of every term of f is in the interval [C log log n, C log n] for some appropriate constant C. Assume also that for every w, there are at most 3 w terms of degree w. For this case, we return to an older approach based on symmetric polynomials [16,17,24], introduced by Gopalan et al. [16]. The idea is as follows. Let Z ∈ {0, 1} n indicate which variables will remain alive. For convenience, for any {0, 1}-valued function f , let f = (-1) f . Having already sampled Z, our remaining task is to argue that the small-bias distribution Y fools the "bias function" defined by
D. Doron, P. Hatami, and W. M. Hoza
Translating {0, 1} to {±1}, the ⊕ operation becomes multiplication, i.e., f = i f i . For independent random variables, product and expectation can be interchanged, so the bias function of f is the product of the bias functions of the f i -s. Define f i so that the bias function of
The approach used in prior work [16,17,24] is to expand Equation (1) in terms of elementary symmetric polynomials. Recall that for y ∈ R m , the k-th elementary symmetric polynomial S k (y) is defined by
We can expand Equation (1) as
Therefore, the error of our pseudorandom restriction is captured by
). Now we can reason as follows. Pick a cutoff point k 0 .
For k ≤ k 0 , we do a Fourier L 1 calculation to show that S k ( f 1 , . . . , f m ) has near-zero expectation even under the small-bias distribution Y .
For k ≈ k 0 , we do a variance calculation to show that S k ( f 1 , . . . , f m ) is small with high probability under the uniform distribution, hence also under Y by the previous L 1 calculation.
Finally we invoke a tail bound [17], which says that if S k0 and S k0+1 are both small, then the sum of all subsequent values is also small. How should we choose the cutoff point k 0 ? If f is a homogeneous F 2 -polynomial of degree w, then we should pick k 0 = Θ( log n w ). That way, k 0 is small enough for the L 1 calculation to work out, because the number of monomials in S k0 (y 1 , . . . , y m ) is
But at the same time, k 0 is large enough to sufficiently dampen
In fact, one can show that
. This is small enough for the tail bound to give an overall error of 1/ poly(n).
The difficulty, of course, is that f is not necessarily homogeneous, i.e., the terms of f do not necessarily all have the same degree. To address this difficulty, following prior work, let us partition the terms of
there is a suitable cutoff point k 0 , so our restriction preserves the expectation of F q . C C C 2 0 2 0 6:6
At this point, the approach taken by prior work has been to invoke a generic XOR lemma (see Lemma 6) to argue that our restriction must also preserve the expectation of the parity of the F q 's, i.e., our test function f . This XOR lemma is a suitable generalization of the fact that the Fourier L 1 norm is submultiplicative. Unfortunately, invoking the XOR lemma would require us to start with a smaller-bias distribution Y . Effectively, to invoke the XOR lemma, we would have to pay a factor of Q in the seed length, which we cannot afford.
Therefore, we take a different approach. Our observation is that ideally, the cutoff point k 0 should guarantee that every product i∈I f i appearing in S k0 ( f 1 , . . . , f m ) involves Θ(log n) of the input variables x 1 , . . . , x n . Intuitively, that's why the right choice is k 0 = Θ( log n w ) for degree w. When the terms of f do not all have the same degree, the products i∈I f i appearing in S k ( f 1 , . . . , f m ) do not all involve the same number of input variables x 1 , . . . , x n , hence there isn't a well-defined correct choice of k 0 . This suggests that Equation (2) is simply not the best expansion of Equation (1).
These observations motivate the definition of subset-wise symmetric polynomials. We defer to Section 2 for the precise definition, but the point is that they allow us to give a more refined expansion of Equation (1), where instead of just keeping track of k (the number of f i -s participating in each monomial of S k ) we keep track of a whole vector k giving the numbers of f i -s from each bucket participating in each monomial of S k . This allows us to define a norm k that measures the number of input variables x 1 , . . . , x n that participate in each monomial of S k ( f 1 , . . . , f m ).
We expand Equation (1) in terms of subset-wise symmetric polynomials by summing over all vectors k:
Now we can cut off this sum at k = Θ(log n). To complete the argument, we extend known tail bounds for elementary symmetric polynomials [17] to the case of subset-wise symmetric polynomials.
So far, we have outlined the proof that our pseudorandom restriction preserves the expectation of the test function f . Our pseudorandom restriction costs O(log n) truly random bits. But our goal is to design a full PRG with seed length O(log n). It seems that one restriction already uses up our entire budget of truly random bits, so how can we afford to iterate the process?
A key insight is that if f only reads n variables (n ≤ n), then a pseudorandom restriction for f ought to only cost O(log n ) truly random bits rather than O(log n). This intuition can be justified using standard constructions of n -wise small-bias distributions [25,3], provided n ≥ log n. (A similar insight was used previously by Lee and Viola [23].) Let C be a constant such that one pseudorandom restriction costs C log n truly random bits.
To simplify the discussion, assume f is homogeneous of degree w = Θ(log n). Each restriction keeps approximately a p-fraction of variables alive. For simplicity, assume that in each term, exactly a p-fraction of variables remain alive, i.e., assume that after i pseudorandom restrictions, the restricted F 2 -polynomial is homogeneous of degree p i w.
We divide into two cases. For the first case, suppose that the number of terms is always at most exponential in the degree. Specifically, suppose the number of terms is at most 16 w , where w is the degree at that stage. In this case, our pseudorandom restrictions get cheaper and cheaper as we go. Quantitatively, after i restrictions, the restricted polynomial reads only n variables, where n = p i w • 16 p i w . Therefore, the cost of restriction i + 1 is only
Therefore, if we do a total of t pseudorandom restrictions, the total cost is bounded by
This geometric sum is bounded by O(w) = O(log n), regardless of t. To optimize the error of our PRG, we choose t = O(log log log n); after this many restrictions, the number of living variables is small enough that we can stop the iteration and apply a prior near-optimal PRG by Lee [22] to finish the job.
For the second case, suppose that at some stage the number of terms is enormous compared to the degree: the degree is w and the number of terms is more than 16 w . This setting was studied previously by Meka, Reingold, and Tal [24], who gave an optimal PRG for any function that can be written as a parity of an enormous number of functions on small disjoint variable sets. Therefore, in this case, we can stop doing pseudorandom restrictions, and instead fool the function outright using the PRG by Meka et al. [24].
Of course we do not know in advance which case we are in, but this difficulty can be resolved by straightforward XORing.
In this section, we will formally define subset-wise symmetric polynomials and prove suitable tail bounds for them. This section can be read on its own, independent of the application to PRGs. We start by recalling known tail bounds for elementary symmetric polynomials.
As a reminder, the k-th elementary symmetric polynomial is defined by
We rely on the following tail bound by Gopalan and Yehudayoff [17]. As discussed in Section 1.5.1, the bound says that if two S k -s in a row are small, then all subsequent S k -s are small.
, we define the following polynomial:
We name these polynomials as subset-wise symmetric polynomials, since for every q ∈ [Q], S k (y) when restricted to the B q variables is a degree k[q] symmetric polynomial.
Throughout this section we fix B = (B 1 , ..., B Q ) to be a partition of [m]. When the partition B is clear from the context, we will simply write S k instead of S k,B . To formulate our tails bounds for the subset-wise symmetric polynomials, we will need the following auxiliary polynomials:
Given c > 1, we will assign each vector k ∈ N Q a weight, defined as
(In our PRG application, B q will be the set of terms with approximately c q input variables, so k (c) will be approximately the number of input variables participating in each monomial of S k , as outlined in Section 1.5.1.) It is easy to verify that the above weight function is indeed a norm; however, we will not be using this observation.
The main result of this section is a tail-bound for subset-wise symmetric polynomials. In Lemma 3, the parameter A is analogous to the "cutoff point" k 0 discussed in Section 1.5.1.
Then, except with probability
Lemma 3 is similar in spirit to Theorem 2: it says that if the "early" subset-wise symmetric polynomials are small (with high probability), then the "late" subset-wise symmetric polynomials are all small (with high probability).
Before moving to the proof of Lemma 3 in the next subsection, here we first give a tail-bound in the case when the input y satisfies some useful properties. We will later prove Lemma 3, by showing that a random Y satisfies these properties with high probability. Given a vector
Our non-probabilistic tail bound goes as follows.
Lemma 4. Suppose c > 1 and Q, A ∈ N satisfy A > max
Then,
Proof. For a fixed ∈ N and q ∈ [Q], define
which is the -th elementary symmetric polynomial applied to (y i ) i∈Bq . Similarly, define
1}, and for each q ∈ Q, let θ q > 0 be the smallest 4 number satisfying
By Theorem 2,
. 4 It is possible that θq = 0 satisfies Equation (3). In this degenerate case, we must have S k[q],q = 0. This implies S k (y) = 0, hence Equation (4) trivially holds.
C C C 2 0 2 0 6:10
Subset-wise symmetric polynomials by design can be expressed as a product of elementary symmetric polynomials, hence
. By our choice of θ q ,
Therefore, there exist disjoint sets
and that for every q ∈ Q,
Multiplying over q ∈ Q, we get
As a result,
To see the second inequality, observe that when
≤ (8e 2/10 5 ) k [q] , and otherwise 8e k
≤ (8e) λ . Summing up over all choices of k we get,
Proof. Let k, Q 1 , and Q 2 be as in the statement of Lemma 4. Using the Cauchy-Schwarz inequality and the concavity of (•) 1/4 , we get
Therefore, by Markov's inequality, except with probability at most 2 -k (c) /256 ≤ 2 -A/2560000 , we have
.
C C C 2 0 2 0 6:12
The above analysis was done for a fixed choice of k, Q 1 , and Q 2 . The number of choices for such k is A Q (which is subexponential in A), and the number of such Q 1 , Q 2 is at most 3 Q (which is a polynomial in A), thus Lemma 3 follows by a union bound. More precisely, one can check that since
Having completed our analysis of subset-wise symmetric polynomials, we now move on to setting the groundwork for our PRG construction and analysis.
Let U n denote the uniform distribution over {0, 1} n . We will simply write
We say that X ε-fools a family F of functions, if it ε-fools every f ∈ F.
A parity function is a function of the form f (x) = i∈I x i for some set I ⊆ [n]. We say that a random variable Y ∈ {0, 1} n is δ-biased if it δ-fools all parity functions. We say that Y is n -wise δ-biased if it δ-fools all parity functions on at most n bits, i.e., all parity functions with |I| ≤ n . There are explicit constructions of n -wise δ-biased distributions that can be sampled with O(log(n /δ) + log log n) truly random bits [25,3].
Recall that for a function f :
Functions with bounded L 1 norm are fooled by small-bias distributions:
We will also rely on the following "XOR lemma" for small-bias distributions.
Lemma 6 ([16, 24]).
depend on disjoint variable sets, and define
If every δ-biased distribution ε-fools every f i , then every δ k -biased distribution fools f with error 16 k • 2ε.
For p ∈ [0, 1], let Bernoulli(p) ⊗n denote the distribution over {0, 1} n where the bits are i.i.d. and each bit has expectation p. For example, U n = Bernoulli(1/2) ⊗n . For a set
We say that Z ∈ {0, 1} n is γ-almost k-wise independent with marginals p if for every set I ⊆ [n] with |I| ≤ k, the total variation distance between Z| I and Bernoulli(p) ⊗|I| is at most γ. Claim 7. For every n, k, C ∈ N and γ > 0, there is an explicit γ-almost k-wise independent distribution with marginals p = 1-2 -C that can be sampled with O(Ck +log(1/γ)+log log n) truly random bits.
Proof. Sample Y ∈ {0, 1} Cn from a (Ck)-wise (2 -Ck/2-1 γ)-biased distribution. Note that as discussed above Y can be sampled using
truly random bits. Divide Y into n blocks Y (1) , . . . , Y (n) ∈ {0, 1} C , and set
To prove correctness, let f : {0, 1} n → {0, 1} be any test function depending on only k variables. There is a function g : {0, 1} Cn → {0, 1} depending on only Ck variables such that
The expectation parameter p can be "amplified" by drawing independent samples and combining with a coordinate-wise conjunction: Claim 8. Let Z be γ-almost k-wise independent with marginals p. Draw t independent samples z (1) , . . . , z (t) ∼ Z, and let Z = z (1)
Proof sketch. The proof is a simple hybrid argument. Draw t independent samples r (1) , . . . , r (t) ∼ Bernoulli(p) ⊗n , and let
One can show by induction on i that Z (i) is (iγ)-almost k-wise independent with marginals p t .
Recall that our main result (Theorem 1) is a PRG for read-once depth-2 AC 0 [⊕]. For most of the paper, we will focus on the special case that the root gate is ⊕ and its immediate children are ∧ gates. That is, define a PARITY • AND formula to be a function of the form
where each f i is a conjunction of literals, i.e., variables or their negations. We refer to f 1 , . . . , f m as the terms of f . We say that the formula is read-once if each variable x i appears in at most one term. Most of our effort will be spent fooling read-once PARITY • AND formulas. Note that this is a slight generalization of read-once F 2 -polynomials due to the availability of ¬ gates. We will explain in Section 5.6 why it is sufficient to focus on this special case.
The width of a term is the number of variables in the term; the width of f is the maximum width of its terms. The length of f is m, the number of its terms.
For convenience, if f is a function taking values in {0, 1}, we let f = (-1) f . That way, if f is a PARITY • AND formula,
A restriction is a string x ∈ {0, 1, } n ; intuitively, x i = means that x i has still not been assigned a value. We define an associative composition operation on restrictions by the formula
For a function f on {0, 1} n , the restricted function f | x on {0, 1} n is defined by
A restriction x can be specified by two strings y, z ∈ {0, 1} n using the following notation 5 . Define Res : {0,
In words, z indicates the positions, and y provides the bits in the non-positions.
Let Y, Z be distributions over {0, 1} n , and let X = Res(Y, Z). For a function f : {0, 1} n → R, we say that the distribution X preserves the expectation of f with error ε if
where + denotes addition over F n 2 and ∧ denotes coordinate-wise conjunction. This second condition is the "pseudorandomness plus noise" perspective [18] (the string Z ∧ U can be thought of as a noise vector.)
If f takes on values in {0, 1}, for each particular value z that Z might take on, we define the bias function [16]
(We use f rather than f simply for convenience.) The statement that X preserves the expectation of f with error ε is also equivalent to the condition
When z is clear from context, we will just write f instead of f z .
If X is a distribution over {0, 1, } n and t ∈ N, let X •t denote the distribution over x ∈ {0, 1, } n obtained by drawing independent samples x (1) , . . . , x (t) ∼ X and composing them, x = x (1)
Suppose F is a class of Boolean functions that is closed under restriction. If X preserves the expectation of every f ∈ F with error ε, then X •t preserves the expectation of every f ∈ F with error tε. Furthermore, informally, if X "has -probability p", then X •t "has -probability p t ". To be precise, we can consider the case X = Res(Y, Z) where Z is γ-almost k-wise independent with marginals p. Then the distribution of positions in X •t is described by Claim 8.
In this section, we prove that the expectation of a PARITY • AND formula is preserved under a suitable pseudorandom restriction. The cost of the restriction is only O(log n) truly random bits, the error is exp(-Ω(log n)) (near-optimal), and the restriction assigns values to a constant fraction of the inputs.
Set C = 500, C = 2000C, c = 1.1, and β = 0.95, and consider the following two distributions.
Let Y be a δ 3 -biased distribution over {0, 1} n for δ = min n -12C , 1 2 n -5c c-1 -1
= n -12,000,000 . 6 Let Z be a γ-almost k-wise independent distribution over {0, 1} n with marginals p = 1 -2 -C , for k = 6 log n and γ = n -9 . Our restriction is Res(Y, Z), i.e., Z indicates where to put and Y fills in the non-bits. Lemma 9. Let f be a read-once PARITY • AND formula over n variables of width at most C log n. Then, Res(Y, Z) preserves the expectation of f to within error 2 -C log n log log n , i.e.,
Toward proving Lemma 9, we first set some preliminary notations. Recall that f is of the form
where every literal ij is either some variable in {x 1 , . . . , x n } or its negation. 6 No attempt was made to optimize the constants.
C C C 2 0 2 0
Log-Seed Pseudorandom Generators via Iterated Restrictions
We partition the terms of f into Q buckets according to their width. Namely, for each q ∈ [Q] we define the interval I q = [c q-1 , c q ) and define B q ⊆ [m] to be the set of indices i such that w i ∈ I q . Also, for q ∈ [Q] we define
We divide into two cases (Section 4.3 and Section 4.4) depending on whether there exists a bucket with substantially many terms. Lemma 9 will follow immediately from Lemma 10 and Lemma 15, which cover these two cases respectively.
Say that bucket q ∈ [Q] is heavy if both m q > 3 c q and m q > log C n. The first case is that there exists a heavy bucket (i.e., there are many terms of roughly the same width, even relative to q). In this case, we will argue that f itself is balanced and also that it stays balanced, w.h.p., after a pseudorandom restriction.
Lemma 10. Let f be a read-once PARITY • AND formula over n variables of width at most C log n. Suppose there exists a heavy bucket as defined above. Then, with probability at least 1 -
Toward proving Lemma 10, let us define a few more auxiliary notations. Write
where q is a heavy bucket.
Claim 11. It holds that E[f ] ≤ 1 4n .
Proof. By the read-once property and the fact that f rest is bounded,
Each term in F q has width at least c q-1 , so
Recalling that m q ≥ 3 c q , we have 2 -c q-1 ≥ m γ q for γ = log 3 2 c -1 < 3 4 . Thus, using that fact that m q ≥ log C n,
Next, we must analyze the bias of f after the pseudorandom restriction. Let n q be the number of variables read by F q . Let b = log 3 n q . We will group the terms of F q into blocks, each of which reads roughly b variables. To define this grouping, first observe that b ≥ log 3 m q , as each term reads at least one variable. Recalling that c q < log 3 m q , we know that b > c q . Therefore, since each term in F q has width at most c q , we can write
where each block g i reads b i variables for b i ∈ b -1 2 c q , b + 1 2 c q . Let us now estimate B, the number of blocks. Since b > c q , b i ∈ b 2 , 3b 2 . Also, m q > log C n so b > C 2 log log n. Thus, on the one hand,
and on the other hand, B ≤ n q ≤ 3 b . Toward arguing that f is balanced after pseudorandom restrictions, we wish to show that with high probability, z ∼ Z keeps many variables in many terms alive.
n and a formula f , we say f is good under z if z assigns 1 to at least a (1 -β)-fraction of the variables f reads.
Claim 13. For a fixed z ∈ {0, 1} n , let X z ⊆ [B] be the set of blocks g i that are not good under z. Then, with probability at least 1 -1 2n over z ∼ Z,
be some subset of cardinality k 0 . We first bound the probability p that every block g i for i ∈ S is bad under z ∼ Z. For a truly random z ∼ Bernoulli(1 -2 -C ) ⊗n , the above probability is bounded by
, k ≥ k 0 b i so for z ∼ Z, we get that p ≤ n -8 + γ ≤ 2n -8 . Thus, by the union bound, with probability at most
there will be some S whose all blocks are bad. Taking the contrapositive, we infer that with probability at least 1 -1 2n over z ∼ Z, at most k 0 of the g i -s are bad under z.
Proof. Fix a good z, for which at most 4 log n b of the g i -s are not good under it. By Claim 13, z is good with probability at least 1
For every i ∈ B alive , set the following notations. Define the function h i so that h i (y) = 1 if g y i is a nonconstant function, and 0 otherwise. Namely,
where y j is either y j or ¬y j depending on whether y j appears positively or negatively in g i . Also, define
where the sum is over the reals. Denote
The spectral norm of the AND function is 1, and so by the sub-additivity we get that
By the sub-multiplicativity of the spectral norm we have that
. By Claim 5, Y ε-fools the function ∆S , so
Next, observe that ∆S(U ) is the sum of zero-mean independent random variables, as the h i -s are supported over disjoint set of variables. Set A = |B alive | • 2 -4βb . By the Chernoff bound, 2 . Next, we observe that
As b ≤ Cb log n log B ≤ C log n, we can conclude that 2 b ≥ 4βb and so e
Using Equation (5) and the above bound yields a bound on E ∆S(Y ) . By Markov's inequality,
where we have used the fact that b ≥ C log n 4 . Overall, with probability at least 1 -1 2n over y ∼ Y , g y i is nonconstant for at least µ 2 of the i-s, and recall that each such g y i is over at least (1 -β)b i variables. Fix such a good y, and let G ⊆ [B alive ] be the set of nonconstant g y i -s. Again, we can write
Similarly to Claim 11, in order to bound the bias of f | Res(Y,Z) it is sufficient to bound the bias of t 1 , and so
Using the fact that µ
200 b , we get
Proof of Lemma 10. Finally, the fact that with probability at least 1-
n , follows immediately from Claim 11 and Lemma 14.
In this subsection, we prove that a single pseudorandom restriction preserves the expectation in the case where there is no such a heavy B q . Namely, for every q ∈ [Q], either m q ≤ 3 c q or m q ≤ log C n (or both).
Let f be a read-once PARITY • AND formula over n variables in which the width of every term is at most C log n, and in which there are no heavy buckets as described above. Then, with probability at least 1
Toward proving Lemma 15, we partition the Q buckets into two sets and treat terms that fall into each set of buckets separately. Namely, define the two sets as follows.
A = q ∈ [Q] : m q ≤ log 2C n . We refer to these buckets as the sparse buckets.
We refer to these buckets as the well-behaved buckets.
For each set T ∈ {A, B} we denote
and so f = f A ⊕ f B . The next two subsections will be devoted to proving that the expectation of each f T is preserved after a single pseudorandom restriction. In Section 4.4.3 we will combine the two results using the XOR lemma for small-bias distributions (Lemma 6) to prove Lemma 15.
For the sparse buckets, we will follow the Forbes-Kelley approach [14] to prove the following.
As outlined in Section 1.5.1, Lemma 16 follows readily from the work by Forbes and Kelley [14]. We require our restriction to work with high probability over z ∼ Z, not merely in expectation, so we must redo some of Forbes and Kelley's analysis. (No substantial modification is needed.) The details follow.
Proof of Lemma 16. First, recall that each term in f A is of width at most C log n. There are at most log 2C n terms in each bucket, and at most Q = O(log log n) such buckets, so overall f A reads at most n = log 2C+2 n variables.
Note that f A can be computed by a width-4 ROBP of length n . We follow [14] and let G : {0, 1}
n → R 4×4 encode the transition of the branching program. Namely, perhaps after renumbering the variables, we have
where L has degree 7 less than k 0 , H i is of degree exactly k 0 , G >i is a width-4 ROBP, and H i and G >i are on disjoint set of variables. More specifically,
and
where
Just as in [14], the low-degree term L is dealt with a δ-biased distribution. From the work of Chattopadhyay, Hatami, Reingold, and Tal [9] we know that
for some universal constant c CHRT ≥ 1. Thus, by Claim 5, we get that the first term of Equation ( 7) is bounded by
taking into account the fact that E[L(U )] = 0.
For each i of the second term of Equation ( 7), we use sub-multiplicativity and the fact that H i and G >i are on disjoint set of variables to get
Continuing the above bound, by Cauchy-Schwarz we get
Following [14, Lemma 7.1] 8 , using the bound by Chattopadhyay et al. [9] and Parseval's identity [14, Proposition 3.1], we get
Overall, we get that
and we can choose the encoding G so that f A (x) = G(x) 1,1 . Markov's inequality completes the proof. 8 Forbes and Kelley [14] take the bits of Z to have marginals p = 1 2 , but one can extend the lemma easily for the case of a general p.
We will use our tail bounds for subset-wise symmetric polynomials to prove the following lemma.
Lemma 17. With probability at least 1 -1 2n over z ∼ Z, f B can be written as f B = f B ⊕ f B , where f B and f B are over disjoint set of variables, and for every g ∈ {f B , f B } it holds that
The proof of Lemma 17 will follow immediately from Claim 20 and Lemma 21. Toward proving the above lemma, let us set some preliminaries.
Proof. The upper bound on c q follows immediately from the assumption in Lemma 15 that every term has width at most C log n. Also, m q > log 2C n since q / ∈ A. Since we are at Case II, m q > log 2C n implies that m q ≤ 3 c q . From the fact that log 2C n < 3 c q we get c q > log 3 (log 2C n) > C log log n.
Recall that a term f i is good under z if the variables read by f i intersects with z in at least 1 -β fraction.
Claim 19. For a fixed z ∈ {0, 1} n , let X z ⊆ [m] be the set of terms in f B that are not good under z. Then, with probability at least 1 -1 2n over z ∼ Z,
Proof. The proof is very similar to Claim 13. Fix a bucket q ∈ B, set k q = 3 log n c q and observe that k ≥ k q . Let S ⊆ B q be some subset of cardinally k q . We first bound the probability p that every term f i for i ∈ S is bad under z ∼ Z.
For a truly random z ∼ Bernoulli(1 -2 -C ) ⊗n , the above probability is bounded by
For z ∼ Z, we get that p ≤ n -9 + γ ≤ 2n -9 . Thus, with probability at most mq kq p over z ∼ Z there exists a set of k q terms in B q whose all terms are bad under z. By using Claim 18, we get
Moreover, with probability at most |B|n -3 ≤ n -2 over z ∼ Z there exists a q ∈ B and a set of k q terms in B q whose all terms are bad under z. Taking the contrapositive, we infer that with probability at least 1 -n -2 ≥ 1 -1 2n over z ∼ Z, we have at most
terms that are bad for z.
D. Doron, P. Hatami, and W. M. Hoza
From here onwards, we fix a z satisfying
where
is the set of all terms that belong to B's buckets. Simply put, we divide f B to the parity of exceptional terms f B and non-exceptional terms f B for whom we will refer to as good terms. We stress that both f B and f B depend on z.
Claim 20 (Exceptional terms).
Proof. For brevity, let g = f B . For a fixed w ∈ {0, 1} n , let g w (x) = g(x + w). The proof will follow from bounding the spectral norm of g w . Indeed, g w is a multiplication of at most 3c c-1 log n terms, each of which has spectral norm at most 3. By sub-multiplicativity,
Fooling g w is sufficient to fool g z . To see this, note that
where U is an independent copy of U .
Next, we prove:
Lemma 21 (Good terms).
Proof. For brevity, let g = f B and recall that its set of terms is given by C \ X z . Shifting the bias function g = g z to mean zero, recall that we define
Thus, we can write
I⊆C\Xz i∈I
where by K(I) = k we mean that for every q ∈ [Q], there are k[q] terms in I that belong to the q-th bucket, i.e., |I ∩ B q | = k[q]. For simplicity, we reorder the terms of g and write
is the set of terms in g that belong to the q-th bucket. We abbreviate g = ( g 1 , . . . , g m ), and write
C C C 2 0 2 0 6:24
Let I g (x) be the Boolean-valued function which is 1 if and only if
where
. Section 4.4.4 will be devoted to showing that E[I g (Y )] is very close to 1. Namely, Lemma 22. The following two inequalities hold.
For now, let us take Lemma 22 as given and continue with the proof of Lemma 21. We proceed by writing
By Lemma 22, we have that Pr
and set
We bound ∆ as follows.
By definition, the second term is at most 2 -A 1024 . The first term, call it ∆ 1 , can be split into two terms as follows.
D. Doron, P. Hatami, and W. M. Hoza 6:25
where the last inequality follows from the triangle inequality followed by Cauchy-Schwarz. By Lemma 22, the second term of Equation ( 11), ∆ 1,2 , is at most
To finish bounding ∆ 1 , it is left to bound the first term of Equation ( 11), denoted by ∆ 1,1 .
Proof. The proof goes by bounding the spectral norm of the function S k ( g(x)). As for every k ∈ N Q with k (c) = 0, E[S k ( g(U ))] = 0, the claim will follow by using Claim 5, together with sub-additivity and sub-multiplicativity. First, note that:
we get L 1 ( h i ) ≤ 1 as every shift of h i is a negated conjunction of literals. Thus, L 1 ( h i ) ≤ 3 and L 1 ( g i ) ≤ 4.
Recall that Claim 18 tells us that m q ≤ 3 c q , so
Finally,
and the claim follows by observing that δ ≤
and the desired result.
Here we finally incorporate Lemma 16 and Lemma 17.
Proof of Lemma 15. By Lemma 16 and Lemma 17, with probability at least 1
where the three functions are over disjoint set of variables, and it holds that for each T ∈ {A, B, B },
for any δ-biased distribution Y . Using the XOR lemma for small-biased spaces (see Lemma 6), taking into account that our distribution Y is in fact δ 3 -biased, we conclude that
and the lemma follows.
We keep using the notations of Section 4.4.2. Specifically, recall that g = f B = i∈[m ] g i for m = |C \ X z |, and for q ∈ [Q], B q ⊆ [m ] is the set of terms in g that belong to the q-th bucket. Also, for g = ( g 1 , . . . , g m ),
Recall that I g (x) ∈ {0, 1} is 1 if and only if
where
Proof of Lemma 22. As in Section 2, we define
By Lemma 3, to prove the bound on Pr[I g (Y ) = 0] it is sufficient to prove that for every
By now a standard course of action, we aim at bounding the spectral norm of the function R k ( g), together with its expectation under the uniform distribution. To this end, let us define, for q ∈ [Q] and an integer ,
First, we record that:
Proof. Let V i ⊆ [n] be the set of variables read by g i , of cardinality w i , and let i = |V i ∩ {j ∈ [n] : z j = 1}| be the number of live variables read by g i . Note that
Then,
and note that
The fact that Var[
finishes the proof.
Now,
Plugging it in our expression for R k , we get
Finally, let us bound L 1 (R k ( g)). In Equation ( 12) we established the fact that L 1 (S k ( g)) ≤ 12 k (c) ≤ 12 A . Thus,
C C C 2 0 2 0 6:28
Note that δ ≤ 1 32 n -10C 2 -A 4 . Thus, by Claim 5,
and we are done with bounding Pr
So far, we have shown how to pseudorandomly assign values to a constant fraction of the inputs of any read-once PARITY • AND formula using O(log n) truly random bits, preserving the expectation of the formula to within near-optimal error. In this section, to complete the of Theorem 1, we show how to pseudorandomly assign values to all the inputs, i.e., we give a genuine PRG.
For convenience, we make the following definitions.
Definition 26. Let w > 0. A w-proper formula is a read-once PARITY • AND formula of width at most w and length most 2 8w . We say that such a formula is short if its length is at most 2 4w ; otherwise, we say that the formula is long.
Our main goal is to fool (C log n)-proper formulas, but along the way, we will obtain a PRG for w-proper formulas with seed length O(w) and error exp(-Ω(w)), even for w substantially smaller than log n.
Recall that Lemma 9 provides a pseudorandom restriction that uses only O(log n) truly random bits. We now generalize this fact in two respects. First, in the case of w-proper formulas (log log n ≤ w ≤ C log n), we improve the seed length to O(w). Second, in the case of short w-proper formulas, we argue that the restriction simplifies the formula, in the sense that it transforms it into a (w/2)-proper formula.
Lemma 27. For every w, n ∈ N with w ≤ C log n, there is a distribution X over {0, 1, } n with the following properties.
There is an explicit algorithm to sample from X using just O(w + log log n) truly random bits.
If f is a w-proper formula, then X preserves the expectation of f with error exp(-Ω(w/ log w)).
Proof. Let n = 2 8w • w. Let Y be an n -wise δ 3 -biased distribution where δ = (n ) -12C , and let Z be γ-almost k-wise independent with marginals 1 -2 -C , where k = 6 log n and γ = (n ) -9 . Our restriction is X = Res(Y, Z) •2 C+4 .
By standard constructions [25,3] and Claim 7, X can be explicitly sampled using O(w + log log n) truly random bits. Now, to prove expectation preservation, let f be a w-proper formula. By w-properness, there is some set of indices I ⊆ [n], |I| ≤ n , such that f (x) only depends on x| I . Let g : {0, 1} |I| → {0, 1} be the w-proper formula such that f (x) = g(x| I ). Since Y | I is δ 3biased and Z| I is γ-almost k-wise independent with marginals 1 -2 -C , Lemma 9 implies that Res(Y | I , Z| I ) preserves the expectation of g with error exp(-Ω( log n log log n )), which is exp(-Ω(w/ log w)). It follows that Res(Y, Z) preserves the expectation of f with the same error. The error of X is only larger by a constant factor 2 C+4 , because any restriction of a w-proper formula is trivially another w-proper formula.
Finally, to prove simplification, let f be a short w-proper formula, and let f i be a term. Since k > w/2, by Claim 8, the probability that more than w/2 variables from f i are assigned by X is bounded by
The number of terms in f is at most 2 4w , so by the union bound, except with probability 2 -w , f | X has maximum width at most w/2. Furthermore, restricting cannot increase the number of terms, so the number of terms is still bounded by 2 4w = 2 8(w/2) . Therefore, in this case, f | X is (w/2)-proper.
The simplification clause of Lemma 27 only applies if f is short. If f is long, we will therefore need a different approach. We will take a similar approach as Meka, Reingold, and Tal [24].
A full PRG for long w-proper formulas follows readily from their work.
Lemma 28 ([24]). For every w, n ∈ N, there is an explicit (2 -w )-PRG for long w-proper formulas with seed length O(w + log log n).
Proof sketch. In short, the PRG is one of the PRGs by Meka et al. [24, full version, Lemma 6.2], except we replace every δ-biased distribution with a (•)-wise δ-biased distribution to optimize the seed length.
In more detail, let n = 2 8w • w. Sample v ∈ {0, 1} wn from an (n w)-wise (c -w MRT )-biased distribution, where c MRT is a suitable constant. Think of v as n blocks of w bits. Define a set I ⊆ [n] as follows: include i in I if and only if the i-th block of v is 1 w . Sample x (0) , x (1) , . . . , x (16) ∈ {0, 1} n independently from an (n )-wise (c -w MRT )-biased distribution. The PRG outputs the string x defined by
By standard constructions [25,3], the seed length of this PRG is
As for correctness, let f be a long w-proper formula. Let J ⊆ [n] be the set of indices of variables that f reads, so there is some long w-proper formula g on |J| input bits such that f (x) = g(x| J ). Let X be the distribution output by the PRG. Since |J| ≤ n , the w ≤ log |J|. Therefore, X| J fools g with error 2 -w , and hence X fools f with error 2 -w .
For short proper w-formulas, to get a full PRG, we will iterate the restriction of Lemma 27 several times, assigning values to more and more variables. Eventually, we'll stop this recursive process and use a different PRG. Specifically, for the "base case," we'll use a PRG by Lee [22] with minor modifications: Lemma 29 ([22]). For every w, n ∈ N and every ε > 0, there is an explicit ε-PRG for w-proper formulas with seed length O((w + log(1/ε)) • (log w + log log(1/ε)) 2 ) + poly(log log(n/ε)).
Proof sketch. In short, the PRG is one of the PRGs by Lee [22,Theorem 6], except we replace every δ-biased distribution with a (•)-wise δ-biased distribution to optimize the seed length, just like the proofs of Lemma 27 and Lemma 28.
To give a little more detail, let n = 2 8w • w; a w-proper formula only reads n variables. Lee's PRG [22,Theorem 6] is designed to fool arbitrary-order combinatorial checkerboards, i.e., parities of functions on disjoint variable sets of size at most w. This class includes w-proper formulas as a special case. Lee's original PRG has seed length O((w + log(n/ε)) • (log w + log log(n/ε)) 2 ).
After making suitable replacements, one can show that the seed length is reduced to O((w + log(n /ε)) • (log w + log log(n /ε)) 2 ) + poly(log log(n/ε)).
(We omit the full proof, since it repeats much of Lee's analysis [22].) Plugging in the value of n , we get the claimed seed length.
We now give our full PRG for general formulas of width at most C log n. The PRG follows a similar approach to one of the PRGs by Meka et al. [24, full version, Algorithm 3]: iteratively apply the restriction of Lemma 27, but at each step, XOR with the PRG of Lemma 28 in case the formula is long. We recursively define a PRG G w for w-proper formulas, w 0 ≤ w ≤ C log n, as follows.
(Base case) If w ≤ 2w 0 , then G w is the (2 -w0 )-PRG of Lemma 29 based on Lee's work [22]. (Recursive case) If w > 2w 0 , sample X ∈ {0, 1, } n from the distribution guaranteed by Lemma 27 based on the work in Section 4. Sample Y ∈ {0, 1} n using the PRG of Lemma 28 based on Meka et al.'s work [24]. Recursively sample G w/2 , and set
For the analysis, observe first that in the base case w ≤ 2w 0 , G w fools w-proper formulas with error 2 -w0 . Now, for the inductive step, consider some w > 2w 0 . Assume G w/2 fools w/2 -proper formulas with error ε w/2 ; we will show that G w fools w-proper formulas with error ε w , where ε w = ε w/2 + 2 -Ω(w/ log w) .
Let f be a w-proper formula, and for brevity, let G = G w/2 . For the first case, suppose f is long. Any shift of f is also a long w-proper formula, so
For the second case, suppose f is short. For each y ∈ {0, 1} n , define f y (x) = f (y ⊕ x), another short w-proper formula. Fix y ∼ Y , and let E be the event that f y | X is (w/2)-proper, so whether E occurs depends only on X. Then Let ε w be the final right-hand side, so indeed ε w = ε w/2 + exp(-Ω(w/ log w)).
Then
Now, let us add up all these errors. Since w ≥ w 0 always holds, we have ε w ≤ ε w/2 + exp(-Ω(w 0 / log w 0 )). Starting at w = C log n, we only need to halve w a total of O(log log log n) times to reach the base case w ≤ 2w 0 . Therefore, the total error of G C log n is bounded by 2 -w0 + 2 -Ω(w0/ log w0) • O(log log log n) = 2 Finally, let us bound the seed length of G w . In the base case w ≤ 2w 0 , by our choice of w 0 , the seed length s w of G w is bounded by some value s base ≤ O(log n). In the recursive case w > 2w 0 , the seed length s w of G w is bounded by s w = s w/2 + O(w + log log n) = s w/2 + O(w).
The point is that this is essentially a geometric series. More precisely, let c seed be a constant such that s w ≤ s w/2 + c seed • w for all w > 2w 0 . Then by induction, for all w ≥ w 0 , we have
The careful reader will notice a slight discrepancy between the exact constants of Theorem 2 on the one hand and the statements by Gopalan and Yehudayoff[17] and Meka et al.[24] on the other. This discrepancy reflects a minor mistake in the original paper by Gopalan and Yehudayoff[17] that we have here corrected.
With apologies, we here flip the order of the arguments to Res compared to the notation used in the authors' prior work[13].