Authors Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2018
Pseudorandom Generators from
Polarizing Random Walks
Eshan Chattopadhyay∗ Pooya Hatami† Kaave Hosseini‡
Shachar Lovett§
Received July 2, 2018; Revised May 21, 2019; Published October 21, 2019
Abstract: We propose a new framework for constructing pseudorandom generators for
n-variate Boolean functions. It is based on two new notions. First, we introduce fractional
pseudorandom generators, which are pseudorandom distributions taking values in [−1, 1]n .
Next, we use a fractional pseudorandom generator as steps of a random walk in [−1, 1]n that
converges to {−1, 1}n . We prove that this random walk converges fast (in time logarithmic in
n) due to polarization. As an application, we construct pseudorandom generators for Boolean
functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for
functions with sensitivity s, whose seed length is polynomial in s. Other examples include
functions computed by branching programs of various sorts or by bounded-depth circuits.
ACM Classification: F.1.3
AMS Classification: 68Q17
Key words and phrases: pseudorandom generator, random walk
A conference version of this paper appeared in the Proceedings of the 33rd Computational Complexity Conference (CCC
2018) [5].
∗ Part of this work was done while the author was also affiliated with the Institute for Advanced Study, Princeton supported
by NSF grants CCF-1412958, CCF-1849899 and the Simons foundation.
† Supported by a Simons Investigator Award (#409864, David Zuckerman).
‡ Supported by NSF grant CCF-1614023.
§ Supported by NSF grant CCF-1614023.
© 2019 Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a010
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
1 Introduction
Pseudorandom generators (PRG) are widely studied in complexity theory. There are several general
frameworks used to construct PRGs. One is based on basic building blocks, such as small-bias genera-
tors [16, 2], k-wise independence, or expander graphs [11]. Another approach is based on the hardness vs.
randomness paradigm, which was introduced by Nisan and Wigderson [18] and has been very influential.
Many of the hardness results used in the latter framework are based on random restrictions, and the
analysis of how they simplify the target class of functions. The number of papers in these lines of work is
on the order of hundreds, so we do not even attempt to give a comprehensive survey of them all; instead
we refer the reader to survey articles [7, 24].
The purpose of this paper is to introduce a new framework for constructing PRGs based on polarizing
random walks. We develop the theory in this paper and give a number of applications; perhaps the most
notable one is a PRG for functions of sensitivity s whose seed length is polynomial in s. But, as this is
a new framework, there are many questions that arise, both technical and conceptual, and we view this
paper as mostly preliminary, with the hope that many more applications would follow.
1.1 PRGs and fractional PRGs
Let F be a class of Boolean functions f : {−1, 1}n → {−1, 1}. The standard definition of a PRG for F
with error ε > 0, is a random variable X ∈ {−1, 1}n such that
∀ f ∈ F, |EX [ f (X)] − EU [ f (U)]| ≤ ε,
where U denotes a random variable with the uniform distribution in {−1, 1}n . We relax this definition by
introducing a new object called a fractional PRG, defined in the next paragraph.
To prepare the notation for the definition, identify f with a real multilinear polynomial, namely its
Fourier expansion. This extends f : {−1, 1}n → {−1, 1} to f : Rn → R, although, we would only be
interested in inputs from [−1, 1]n . Observe that if x ∈ [−1, 1]n then f (x) = EX [ f (X)] where X ∈ {−1, 1}n
is a random variable sampled as follows: for every i ∈ [n] sample Xi ∈ {−1, 1} independently with
E[Xi ] = xi . In particular, f on [−1, 1]n is bounded, namely f : [−1, 1]n → [−1, 1]. Also, f (0) = EU [ f (U)].
The following is a key definition.
Definition 1.1 (Fractional PRG). Let f : [−1, 1]n → [−1, 1] be real multilinear. A fractional PRG for f is
a random variable X ∈ [−1, 1]n such that
|EX [ f (X)] − f (0)| ≤ ε.
Moreover, X has seed length r if X = G(U) for some function G : {−1, 1}r → [−1, 1]n .
One trivial construction of a fractional PRG is X ≡ 0 but this is not going to be useful for our purpose
of constructing PRGs. To disallow such examples, we require each coordinate of X to be far from zero
with some noticeable probability. Formally, X ∈ [−1, 1]n is called p-noticeable if E[Xi2 ] ≥ p for all
i = 1, . . . , n.
A good example to keep in mind is the following. Let G : {−1, 1}r → {−1, 1}n be a (Boolean valued)
function, and set X = pG(U), where U ∈ {−1, 1}r is uniform. Notice that X is p2 -noticeable.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 2
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
Fractional PRGs are easier to construct than standard PRGs, as they can take values in [−1, 1]n . For
example, assume that f has Fourier tails bounded in L1 . That is, there exist parameters a, b ≥ 1 for which
∑ | fˆ(S)| ≤ a · bk ∀k = 1, . . . , n.
S⊆[n]:|S|=k
We show (in Lemma 4.4) that if X ∈ {−1, 1}n is roughly (ε/a)-biased, then pX is a fractional PRG for f
with p ≈ 1/b and error ε. The reason is that this choice of p controls all the Fourier coefficients of f with
large Hamming weight, while X controls the ones with small weight. (In fact, to optimize parameters one
can choose X to be almost k-wise independent; see Lemma 4.4 for details). In any case, note that pX is
p2 -noticeable as pX takes values in {−p, p}n .
1.2 Fractional PRG as steps in a random walk
Let X ∈ [−1, 1]n be a fractional PRG for f with error ε. That is,
|EX [ f (X)] − f (0)| ≤ ε.
The goal is to construct a random variable Y ∈ {−1, 1}n such that EY [ f (Y )] ≈ f (0), where the
fractional PRG X provides a “small step” towards this approximation. If we can combine these small
steps in a way that they converge fast to {−1, 1}n , then we would be done. To be a bit more precise,
consider a random walk starting at 0 with the following properties:
1. The value of f at each step on average does not change by too much.
2. The random walk converges fast to {−1, 1}n .
Observe that if we take X as the first step, then property 1 is satisfied for the first step. Considering
later steps leads to the following question: Given a point y ∈ [−1, 1]n , can we find a random variable
A = A(y, X) such that
|E[ f (A)] − f (y)| ≤ ε,
and such that A takes values closer to Boolean values? We show that this is indeed the case if we assume
that X not only fools f , but also fools any possible restriction of f .
To formalize this, let F be a family of n-variate Boolean functions f : {−1, 1}n → {−1, 1}. We
say that F is closed under restrictions if for any f ∈ F, if we fix some inputs of f to constants {−1, 1},
then the new restricted function is still in F. Most natural families of Boolean functions studied satisfy
this condition. Some examples are functions computed by small-depth circuits, functions computed by
bounded width branching programs, and functions of low sensitivity.
We show that if X is a fractional PRG for such F, then it can be used to approximate f (y) for any
y ∈ [−1, 1]n . Define δy ∈ [0, 1]n by (δy )i = 1 − |yi |. For x, x0 ∈ [−1, 1]n define x ◦ x0 ∈ [−1, 1]n to be their
coordinate-wise product, (x ◦ x0 )i = xi xi0 . Note that under this definition, the subcube {y + δy ◦ x : x ∈
[−1, 1]n } is the largest symmetric subcube of [−1, 1]n centered at y.
We show (Claim 3.3) that if X ∈ [−1, 1]n is a fractional PRG for F which is closed under restrictions,
then for any f ∈ F and any y ∈ [−1, 1]n it holds that
|E[ f (y + δy ◦ X)] − f (y)| ≤ ε.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 3
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Technically, we need to also assume that X is symmetric, which means that Pr[X = x] = Pr[X = −x] for
all x. This is easy to achieve from any X which is not symmetric, for example by multiplying X with a
uniform bit (thus, increasing its seed length by 1 bit).
1.3 Polarization and fast convergence
Our next goal is to show fast convergence of the random walk to {−1, 1}n . To that end, we need to
analyze the following martingale:
Y1 = X1 ,
Yi = Yi−1 + δYi−1 ◦ Xi ,
where X1 , X2 , . . . are independent copies of a fractional PRG. We show that for some t not too large, Yt is
close to a point in {−1, 1}n . But why would that be true? This turns out to be the result of polarization in
the random walk. It suffices to show this for every coordinate individually.
So, let Z1 , Z2 , . . . ∈ [−1, 1] be independent random variables (which are the i-th coordinate of X1 , X2 , . . .
for some fixed i), and define the following one-dimensional martingale:
W1 = Z1 ,
Wi = Wi−1 + (1 − |Wi−1 |)Zi .
Claim 3.5 shows that if (i) Zi is symmetric, and (ii) E[Zi2 ] ≥ p (which follows from our assumption that
the fractional PRG is p-noticeable), then it holds that
Pr[|Wt | ≥ 1 − δ ] ≥ 1 − δ
for t = O(log(1/δ )/p). Setting δ = ε/n guarantees that with probability 1 − ε all the coordinates of Yt
are ε/n close to {−1, 1}. Then a simple argument shows that rounding the coordinates gives a PRG with
error O(ε), as desired.
We now state our main theorem.
Theorem 1.2 (Main theorem, informal version of Theorem 2.5). Let F be a family of n-variate Boolean
functions that is closed under restrictions. Let X ∈ [−1, 1]n be a symmetric p-noticeable fractional PRG
for F with error ε. Set t = O(log(n/ε)/p) and let X1 , . . . , Xt be i.i.d. copies of X. Define the following
random variables taking values in [−1, 1]n :
Y0 = 0; Yi = Yi−1 + δYi−1 ◦ Xi i = 1, . . . ,t.
Let G = sign(Yt ) ∈ {−1, 1}n obtained by taking the sign of the coordinates in Yt . Then G is a PRG for F
with error (t + 1)ε.
Note that computing this PRG only involves basic operations such as addition and multiplication over
the reals with bounded error.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 4
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
1.4 PRG for functions with bounded Fourier tails
As mentioned above, the families of Boolean functions that are fooled by our PRG include ones that
satisfy the following two properties: (i) being closed under restrictions; (ii) having bounded L1 Fourier
tails. Tal [22] showed that the latter condition follows from a widely studied condition, that of bounded
L2 Fourier tails. Thus, using existing bounds for L2 Fourier tails, we get that our PRG fools several
classes of Boolean functions. Below we list the results for error ε = O(1), and refer the reader to the
corresponding claims for the details of the full range of parameters:
1. Functions of sensitivity s: seed length O(s3 log log n). The best previous construction due to
Hatami and Tal [10] required seed length subexponential in s (concretely, their dependence on s is
√
exp( s)). See Corollary 4.6 for details.
2. Unordered read-once branching programs of width w: seed length O(log2w+1 n · log log n).
This is quadratically worse than the best known PRG due to Chattopadhyay et al. [6]. However,
our PRG construction does not utilize the branching program structure at all, except to obtain the
Fourier tail bounds. See Corollary 4.7 for details.
3. Permutation unordered read-once branching programs of width w: seed length O(w4 log n ·
log log n). This improves the dependence on n quadratically compared to the previous best PRG
due to Reingold et al. [20]. See Corollary 4.8 for details.
4. Bounded-depth circuits: if f is computed by AC0 circuits of depth d and size poly(n), our PRG
has seed length O(log2d−1 n · log log n). This is quadratically worse than the best known PRG due
to Tal [22]. See Corollary 4.9 for details.
Other than the PRG for functions of low sensitivity, all the other PRGs are comparable to the best
known tailored PRG. However, the main message is that they are all the same PRG. Our general
theorem is the following.
Theorem 1.3 (PRG for functions of bounded L1 Fourier tail, informal version of Theorem 4.5). Let F be
a family of n-variate Boolean functions closed under restrictions. Assume that there exist a, b ≥ 1 such
that for every f ∈ F,
∑ | fˆ(S)| ≤ a · bk .
S⊆[n]:|S|=k
Then, for any ε ≤ 1/poly(b log n) there exists an explicit PRG X ∈ {−1, 1}n which fools F with error
ε > 0, whose seed length is O(log(n/ε)(log log n + log(a/ε))b2 ).
We note again that by a result of Tal [22], Theorem 1.3 holds also if we instead assume a bound on
the L2 Fourier tails (which are more common), namely if we assume that for every f ∈ F it holds that
∑ fˆ(S)2 ≤ a · 2−k/b .
S⊆[n]:|S|≥k
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 5
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
1.5 PRG for functions which simplify under random restriction
A major component in prior constructions of PRGs that are based on random restrictions is finding a much
smaller set of “pseudorandom retrictions.” Ajtai and Wigderson [1] proposed such a PRG for low-depth
circuits. Much follow-up work has been based on this framework to build PRGs for various classes of
functions including low-depth circuits, branching programs, low-sensitivity functions [23, 8, 20, 6, 10],
and a major component of the analysis is proving that the derandomized random restrictions work.
Our framework for constructing PRGs directly applies to function families that simplify under
random restrictions without the need to derandomize the restrictions. Let F be a family of functions
f : {−1, 1}n → {−1, 1} which are extended multilinearly to [−1, 1]n . Fix a parameter 0 < p < 1 and
define the p-averaged function of f , denoted f p : {−1, 1}n → [−1, 1], as follows: sample A ⊆ [n] where
Pr[i ∈ A] = p independently for i ∈ [n], and define
f p (x) = EA,U [ f (xA ,UAc )]
where xA ∈ {−1, 1}A is the restriction of the input x to the coordinates in A, and U ∈ {−1, 1}n is
independently and uniformly chosen. The crucial observation (Claim 5.1) is that for every x ∈ {−1, 1}n it
holds that
f (px) = f p (x).
Suppose now we have a standard PRG X for the class of p-averaged functions F p = { f p : f ∈ F}.
Note a PRG for the p-random restriction of functions in F would do, as f p is a convex combination of
p-random restrictions of f (namely, averaging over U). Then, using our observation above, this implies
that X 0 = pX is a fractional PRG for the class F. Now by using our framework of viewing this fractional
PRG as a random walk step, one can derive a standard PRG for F using O(log(n/ε)/p2 ) independent
copies of X.
1.6 Fourier tails of low-degree F2 polynomials
Viola [25] gave a construction of a pseudorandom generator which fools n-variate polynomials over F2 .
The construction is the XOR of d independent small-bias generators. We wonder whether our framework
can be used to achieve similar bounds. In particular, we raise the following problem: does the class of
low-degree polynomials over F2 have bounded L1 Fourier tails? It’s trivially true for d = 1 and it can be
shown to hold for d = 2. However, to the best of our knowledge nothing was known for d ≥ 3.
We show (see Theorem 6.1 for more details) that for any Boolean function f : {−1, 1}n → {−1, 1}
computed by a F2 -polynomial of degree at most d, the following L1 Fourier tail bound holds:
∑ | fb(S)| ≤ kk 23dk ∀k = 1, . . . , n.
|S|=k
This bound however falls short of implying a PRG using our techniques, and we conjecture that the
correct bound is ckd , for some constant cd = 2O(d) .
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 6
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
1.7 PRGs with respect to arbitrary product distributions
We note the following interesting generalization of our results that is almost direct from our techniques.
Consider the problem of “fooling” a family of functions with respect to an arbitrary product distribution
D on {−1, 1}n (the uniform distribution being a special case). More formally, given a distribution D on
{−1, 1}n and a family of functions F, we say that a random variable X is a PRG for F (with respect to D)
if |E[ f (D)] − E[ f (X)]| ≤ ε.
We show a way to fool functions with respect to arbitrary product distributions.
Corollary 1.4. Let F be a family of n-variate Boolean functions which is closed under restrictions and
let D be any product distribution on {−1, 1}n . Let X ∈ [−1, 1]n be a symmetric p-noticeable fractional
PRG for F with error ε and seed length `. Let t = O(log(n/ε)/p). Then there exists an explicit PRG for
F with respect to D with error tε and seed length t`.
Proof sketch. If D is a product distribution on {−1, 1}n , then E[ f (D)] = f (α), where α = E[D] ∈ [−1, 1]n .
Thus, we now start our random walk (defined by the fractional PRG) from the point α instead of from 0,
and the convergence follows from polarization in exactly the same way.
Thus all our PRG results in fact generalize to PRGs with respect to arbitrary product distributions. To
the best of our knowledge, we are not aware of any non-trivial PRGs against arbitrary product distributions
for the classes of functions we study. We wonder if this notion of fooling arbitrary product distributions
has interesting applications.
1.8 Related work
The line of research closest in spirit to our paper, and which motivated our result, is that of using random
and pseudo-random restrictions to construct PRGs. A good example is due to Gopalan et al. [8] which
uses pseudo-random restrictions to construct PRGs. Our framework can be seen as extending this, as
we do not need to analyze pseudo-random restrictions; instead, we analyze fractional PRGs, where the
restriction happens automatically from the fractional PRG structure, and no derandomization is necessary.
Another line of work is the use of random walks in combinatorial optimization, for example in the
algorithmic versions of Spencer’s theorem [3, 13] and follow-up work. It would be interesting to see if
polarization can be used to speed up random walks in combinatorial optimization as well.
1.9 Open problems
As we give a new framework for constructing PRGs, there are many open problems that arise, both
conceptual and technical.
1.9.1 Early termination
Our analysis requires a random walk with t = O(log(n/ε)/p) steps, each coming from a p-noticeable
fractional PRG. We believe that for some natural families of functions shorter random walks might also
suffice, but we do not know how to show this. We discuss this further in Section 7.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 7
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Open problem 1.5. Find conditions on classes of Boolean functions so that short random walks can be
used to construct PRGs. In particular, are there nontrivial classes where the number of steps is independent
of n?
1.9.2 Less independence
Our analysis of Theorem 2.5 currently requires to assume t independent copies of a fractional PRG X. It
might be possible that these copies can be chosen in a less independent form, where the analysis still
holds.
Open problem 1.6. Can the fractional PRGs X1 , . . . , Xt in Theorem 2.5 be chosen not independently,
such that the conclusion still holds? Concrete examples to consider are k-wise independence for k t, or
using an expander random walk.
1.9.3 More applications
Our current applications follow from the construction of a fractional PRG for functions with bounded
Fourier tails. The fractional PRG itself follows from standard constructions in pseudo-randomness (almost
k-wise independent) adapted to our scenario. It will be interesting to try and find other classes of Boolean
functions for which different constructions of fractional PRG work.
1.9.4 Gadgets
We can view the random walk as a “gadget construction.” Given independent p-noticeable fractional
PRGs X1 , . . . , Xt ∈ [−1, 1]n , view them as the rows of a t × n matrix, and then apply a gadget g : [−1, 1]t →
{−1, 1} to each column to obtain the outcome in {−1, 1}n . We show that the random walk gives such
a gadget which converges for t = O(log(n/ε)/p). Many constructions of PRGs can be viewed in this
framework, where typically Xi ∈ {−1, 1}n . Ours is the first construction which allows Xi to take non-
Boolean values. It is interesting whether other gadgets can be used instead of the random walk gadget,
and whether there are general properties of gadgets that would suffice.
1.9.5 Low-degree polynomials
As discussed above, we wonder if our techniques can be used to construct a PRG for low-degree F2
polynomials. In particular, we ask if one could improve the bounds we obtain (see Theorem 6.1) on the
L1 Fourier tails of low-degree F2 polynomials.
Open problem 1.7. Let f = (−1) p where p : Fn2 → F2 is a polynomial of degree d. Is there a constant
cd such that ∑S:|S|=k | fˆ(S)| ≤ ckd which is independent of n? In particular, we conjecture that cd = 2O(d)
should work.
Note that the exponential dependence on k is needed, as witnessed from the following example:
consider the quadratic F2 polynomial
n/2
q(x) = ∑ x2i−1 x2i .
i=1
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 8
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
n
Then (−1)q has Fourier L1 weight · 2−n/2 = 2Ω(n) on the (n/2)-th level.
n/2
1.10 Paper organization
We describe the general framework in detail in Section 2. We prove Theorem 2.5 in Section 3. We
describe applications in Section 4. Our framework also applies to function families that simplify under
random restrictions. We describe this in Section 5. We prove L1 Fourier tail bounds for low-degree F2
polynomials in Section 6. We try to partially answer the question related to early termination of the
random walk in Section 7.
2 General framework
2.1 Boolean functions
Let f : {−1, 1}n → [−1, 1] be an n-variate Boolean function, identified with its multilinear extension, also
known as its Fourier expansion. For x ∈ [−1, 1]n define f (x) = ∑S⊆[n] fˆ(S)xS where xS = ∏i∈S xi . As f is
multilinear, a convenient viewpoint is to view f (x) as computing the expected value of f on a product
distribution on {−1, 1}n . That is, let W = W (x) ∈ {−1, 1}n be a random variable, where W1 , . . . ,Wn
are independently chosen so that E[Wi ] = xi . Then f (x) = E f (W ). In particular, f (0) = E f (U), where
U ∈ {−1, 1}n is uniformly chosen.
A family F of n-variate Boolean functions is said to be closed under restrictions if for any f ∈ F and
any function f 0 : {−1, 1}n → {−1, 1} obtained from f by fixing some of its inputs to {−1, 1} it holds
that also f 0 ∈ F.
2.2 Pseudorandom generators
Let F be a family of n-variate Boolean functions. The following is the standard definition of a pseudoran-
dom generator (PRG) for F, adapted to our notation.
Definition 2.1 (PRG). A random variable X ∈ {−1, 1}n is a PRG for F with error ε, if for any f ∈ F it
holds that f (0) − E f (X) ≤ ε.
We introduce the notion of a fractional PRG. It is the same as a PRG, except that the random variable
is allowed to take values in [−1, 1]n , instead of only Boolean values. We assume that X has finite support.
Definition 2.2 (Fractional PRG). A random variable X ∈ [−1, 1]n with finite support, is a fractional PRG
for F with error ε, if for any f ∈ F it holds that f (0) − E f (X) ≤ ε.
Our main goal will be to “amplify” fractional PRGs for F in order to obtain PRGs for F. To that
end, we need to enforce some non-triviality conditions on the fractional PRG. For example, X = 0 is a
fractional PRG for any function. We require that for any coordinate i ∈ [n], the value of Xi is far from
zero with noticeable probability. Formally, we require a noticeable second moment.
Definition 2.3 (p-noticeable random variable). A random variable X ∈ [−1, 1]n is p-noticeable if for
every i ∈ [n], E[Xi2 ] ≥ p.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 9
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
For technical reasons, we would also need X to be symmetric, which means that the distribution of
−X is the same as the distribution of X. This is easy to achieve, for example by multiplying all elements
of X with a uniformly chosen sign.
2.3 Polarizing random walks
The main idea is to view a fractional PRG as steps in a random walk in [−1, 1]n that converges to {−1, 1}n .
To that end, we define a gadget that implements the random walk; and moreover, that allows for fast
convergence. As we will see later, the fast convergence is an effect of polarization.
Definition 2.4 (Random walk gadget). For any t ≥ 1 define the random walk gadget gt : [−1, 1]t → [−1, 1]
as follows. Let a1 , . . . , at ∈ [−1, 1]. Define g1 (a1 ) := a1 and for t > 1,
gt (a1 , . . . , at ) := gt−1 (a1 , . . . , at−1 ) + (1 − |gt−1 (a1 , . . . , at−1 )|)at .
We extend the definition to act on bit-vectors. Define gtn : ([−1, 1]n )t → [−1, 1]n as follows. For x1 , . . . , xt ∈
[−1, 1]n define
gtn (x1 , . . . , xt ) = (gt (x1,1 , . . . , xt,1 ), . . . , gt (x1,n , . . . , xt,n )) .
Equivalently, we can view gtn as follows: construct a t × n matrix whose rows are x1 , . . . , xt ; and then
apply gt to each column of the matrix to obtain a resulting vector in [−1, 1]n .
The following theorem shows how to “amplify” fractional PRGs using the random walk gadget to
obtain a PRG. Below, for x ∈ [−1, 1]n we denote by sign(x) ∈ {−1, 1}n the Boolean vector obtained by
taking the sign of each coordinate (the sign of 0 can be chosen arbitrarily).
Theorem 2.5 (Amplification Theorem). Let F be a family of n-variate Boolean functions which is closed
under restrictions. Let X ∈ [−1, 1]n be a symmetric p-noticeable fractional PRG for F with error ε.
Set t = O(log(n/ε)/p) and let X1 , . . . , Xt be iid copies of X. Define a random variable G ∈ {−1, 1}n as
follows:
G := G(X1 , . . . , Xt ) = sign(gtn (X1 , . . . , Xt )).
Then G is a PRG for F with error (t + 1)ε.
3 Proof of Amplification Theorem
We prove Theorem 2.5 in this section. From here onwards, we fix a family F of n-variate Boolean
functions which is closed under restrictions. The proof is based on the following two lemmas. The
first lemma amplifies a p-noticeable fractional PRG to a (1 − q)-noticeable fractional PRG. The second
lemma shows that setting q = ε/n, the latter fractional PRG can be rounded to a Boolean-valued PRG
without incurring too much error.
Lemma 3.1 (Amplification lemma). Let X1 , . . . , Xt ∈ [−1, 1]n be independent symmetric p-noticeable
fractional PRGs for F with error ε. Define a random variable Y ∈ [−1, 1]n as
Y := gtn (X1 , . . . , Xt ).
Then Y is a (1 − q)-noticeable fractional PRG for F with error tε, where q = 2−Ω(pt) .
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 10
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
Lemma 3.2 (Rounding lemma). Let Y ∈ [−1, 1]n be a (1 − q)-noticeable fractional PRG for F with error
ε. Then sign(Y ) ∈ {−1, 1}n is a PRG for F with error ε + qn.
Theorem 2.5 follows directly by applying Lemma 3.1 with t = O(log(n/ε)/p) to obtain q = ε/n and
then applying Lemma 3.2.
3.1 Proof of Lemma 3.1
We prove Lemma 3.1 in this section. We need to prove two claims: that gtn (X1 , . . . , Xt ) is a fractional PRG
for F with error εt, and that it is (1 − q)-noticeable. This is achieved in the following sequence of claims.
First we need some notations. For y ∈ [−1, 1]n define δy ∈ [−1, 1]n by (δy )i := 1 − |yi |. For two
vectors x, y ∈ [−1, 1]n define x ◦ y ∈ [−1, 1]n to be their pointwise product, namely (x ◦ y)i := xi yi . Observe
that {y + δy ◦ x : x ∈ [−1, 1]n } is the largest symmetric subcube in [−1, 1]n centered at y.
Claim 3.3. Let X ∈ [−1, 1]n be a fractional PRG for F with error ε. Then for any f ∈ F and any
y ∈ [−1, 1]n ,
| f (y) − E f (y + δy ◦ X)| ≤ ε.
Proof. Consider a distribution over F ∈ F obtained from f by fixing the i-th input to sign(yi ) with
probability |yi |, independently for each i. That is,
F(x) := f (R(x)),
where R(x) ∈ [−1, 1]n is a random variable obtained by sampling R1 , . . . , Rn independently where each
Ri is chosen as follows. Pick Ri (x) = sign(yi ) with probability |yi | and with probability 1 − |yi | do as
follows: pick Ri (x) = 1 with probability (xi + 1)/2 and pick Ri (x) = −1 otherwise. It’s easy to check that
ER (R(x)) = y + δy ◦ x. By multilinearity of f , and as R(x) is a product distribution, for all x ∈ [−1, 1]n ,
EF [F(x)] = ER [ f (R(x))] = f (ER [R(x)]) = f (y + δy ◦ x).
Setting x = X and averaging over X gives
| f (y) − EX [ f (y + δy ◦ X)]| = EF [F(0)] − EF,X [F(X)] ≤ EF F(0) − EX [F(X)] ≤ ε,
since F ∈ F with probability one and X is a fractional PRG for F with error ε.
Claim 3.4. Let X1 , . . . , Xt ∈ [−1, 1]n be independent fractional PRGs for F with error ε. Then for any
f ∈ F,
f (0) − EX1 ,...,Xt [ f (gtn (X1 , . . . , Xt ))] ≤ tε.
Proof. The proof is by induction on t. The base case t = 1 follows by definition as gn1 (X1 ) = X1 . For
t > 1 we will show that
n
E[ f (gt−1 (X1 , . . . , Xt−1 ))] − E[ f (gtn (X1 , . . . , Xt ))] ≤ ε,
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 11
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
from which the claim follows by the triangle inequality. In fact, we will show a stronger inequality: for
any fixing of x1 , . . . , xt−1 ∈ [−1, 1]n , it holds that
n
f (gt−1 (x1 , . . . , xt−1 )) − EXt [ f (gtn (x1 , . . . , xt−1 , Xt ))] ≤ ε.
The first inequality then follows by averaging over x1 = X1 , . . . , xt−1 = Xt−1 . To see why this latter
n (x , . . . , x
inequality holds, set y = gt−1 1 t−1 ). Then by definition,
gtn (x1 , . . . , xt−1 , Xt ) = y + δy ◦ Xt .
The claim now follows from Claim 3.3.
We have so far proved that gtn (X1 , . . . , Xt ) is a fractional PRG for F with slightly worse error. Al-
though we do not need it, it is worth noting that it is symmetric since X1 , . . . , Xt are symmetric and
−gtn (X1 , . . . , Xt ) = gtn (−X1 , . . . , −Xt ). To conclude, we show that it converges fast to a value close to
{−1, 1}n . This is the effect of polarization. It will be enough to analyze this for one-dimensional random
variables.
Claim 3.5. Let A1 , . . . , At ∈ [−1, 1] be independent symmetric random variables with E[A2i ] ≥ p. For
i = 1, . . . ,t define
Bi := gi (A1 , . . . , Ai ) = Bi−1 + (1 − |Bi−1 |)Ai .
Then E[Bt2 ] ≥ 1 − q where q = 3 exp(−t p/16).
Proof. Let Ci := 1 − |Bi | be the distance to {−1, 1} at step i. We show that Ci converges to 0 exponentially
fast. Observe that Ci satisfies the following recursive definition:
(
Ci−1 (1 − Ai · sign(Bi−1 )) if Ci−1 (1 − Ai · sign(Bi−1 )) ≤ 1,
Ci =
2 −Ci−1 (1 − Ai · sign(Bi−1 )) if Ci−1 (1 − Ai · sign(Bi−1 )) > 1.
In either case one can verify that Ci ∈ [0, 1] and that
Ci ≤ Ci−1 (1 − Ai · sign(Bi−1 )).
Now observe that Ci−1 and Ai · sign(Bi−1 ) are independent. This is because Bi−1 is symmetric (because
A j ’s are symmetric), and so |Bi−1 | and sign(Bi−1 ) are independent. So we can write,
hp i hp i hp i
E Ci ≤ E Ci−1 E 1 − Ai · sign(Bi−1 ) .
√
The Taylor expansion of 1 − x in [−1, 1] is
√ x x2 x3
1−x = 1− − − −....
2 8 16
In particular, all the coefficients except for the constant term are negative. As Ai · sign(Bi−1 ) is symmetric,
E[(Ai · sign(Bi−1 ))k ] = 0 for any odd k, so
hp i E[A2i ] p
E 1 − Ai · sign(Bi−1 ) ≤ 1 − ≤ 1 − ≤ exp(−p/8).
8 8
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 12
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
Thus
hp i t hp i
E Ct ≤ ∏ E 1 − Ai · sign(Bi−1 ) ≤ exp(−t p/8).
i=1
√ √
Now we use Markov’s inequality. We know Pr[ Ct ≥ λ E Ct ] ≤ λ −1 . By choosing λ = exp(t p/16)
we get Pr[Ct ≥ exp(−t p/8)] ≤ exp(−t p/16). If Ct ≤ exp(−t p/8) then 1 − Bt2 ≤ 2 exp(−t p/8). If not,
then we can trivially bound 1 − Bt2 ≤ 1. Putting these together gives
E[1 − Bt2 ] ≤ 2 exp(−t p/8) + exp(−t p/16) ≤ 3 exp(−t p/16).
To provide a piece of intuition explaining the fast convergence of this random walk, notice that once
Ci becomes sufficiently small, it gets more and more difficult to increase the value of Ci again. This could
be best explained with an example. Suppose all Ai ’s take value in {−0.5, 0.5}. We start at B0 = 0 and
take a step, say A1 = 0.5, and therefore B1 = 0.5. Now observe that the length of the next step would be
only (1 − |B1 |)|A2 | = 0.25. So even if A2 = −0.5, we get B2 = 0.25, which means we still need to take
one more step to become less than 0. In other words, once we get close to the boundary {−1, 1}, the
random walk converges faster as it gets more difficult to move away from the boundary.
Corollary 3.6. Let X1 , . . . , Xt ∈ [−1, 1]n be independent symmetric p-noticeable random variables. Define
Y = gtn (X1 , . . . , Xt ). Then Y is (1 − q)-noticeable for q = 3 exp(−t p/16).
Proof. Apply Claim 3.5 to each coordinate of Y .
Lemma 3.1 follows by combining Claim 3.4 and Theorem 3.6.
3.2 Proof of Lemma 3.2
We prove Lemma 3.2 in this section. Let x ∈ [−1, 1]n be a possible outcome of X. Let W := W (x) ∈
{−1, 1}n be a random variable, where W1 , . . . ,Wn are independent and E[Wi ] = xi . Then EW [ f (W )] = f (x).
As f takes values in [−1, 1], we can upper bound | f (x) − f (sign(x))| by
| f (x) − f (sign(x))| = |EW [ f (W )] − f (sign(x))| ≤ 2 Pr[W 6= sign(x)].
The last term can be bounded by the union bound,
n n
2 Pr[W 6= sign(x)] ≤ 2 ∑ Pr[Wi 6= sign(xi )] = ∑ 1 − |xi |.
i=1 i=1
Setting x = X and averaging over X gives
n
|EX [ f (X)] − EX [ f (sign(X))]| ≤ EX | f (X) − f (sign(X))| ≤ ∑ E[1 − |Xi |].
i=1
As X is (1 − q)-noticeable it satisfies E[Xi2 ] ≥ 1 − q for all i. As 1 − z ≤ 1 − z2 for all z ∈ [0, 1] we have
E[1 − |Xi |] ≤ E[1 − Xi2 ] ≤ q.
This concludes the proof as
| f (0) − EX [ f (sign(X))]| ≤ | f (0) − EX [ f (X)]| + |EX [ f (X)] − EX [ f (sign(X))]| ≤ ε + qn,
where the first inequality follows as X is a fractional PRG with error ε, and the second by the discussion
above.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 13
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
4 PRGs for functions with bounded Fourier tails
Several natural families of Boolean functions have bounded Fourier tails, such as: AC0 circuits [12, 15];
functions with bounded sensitivity [9, 14]; and functions computed by branching programs of various
forms [20, 6]. Our goal is to construct a universal PRG which fools any such function. We consider two
variants: L1 bounds and L2 bounds.
Definition 4.1 (L1 bounds). For a, b ≥ 1, we denote by Ln1 (a, b) the family of n-variate Boolean functions
f : {−1, 1}n → {−1, 1} which satisfy
∑ | fb(S)| ≤ a · bk ∀k = 1, . . . , n.
S⊆[n]
|S|=k
Definition 4.2 (L2 bounds). For a, b ≥ 1, we denote by Ln2 (a, b) the family of n-variate Boolean functions
f : {−1, 1}n → {−1, 1} which satisfy
∑ fb(S)2 ≤ a · 2−k/b ∀k = 1, . . . , n.
S⊆[n]
|S|≥k
Tal [22] showed that L2 bounds imply L1 bounds: if f ∈ L2 (a, b) then f ∈ L1 (a, b0 ) for b0 = O(b).
The reverse direction is false, as can be witnessed by the PARITY function. So, the class of functions
with L1 bounded Fourier tails is richer, and we focus on it.
In the following lemma, we construct a fractional PRG for this class, which we will then amplify
to a PRG. We note that this lemma holds also for bounded functions, not just Boolean functions. The
construction is based on a scaling of almost d-wise independent random variables, whose definition we
now recall.
Definition 4.3 (Almost d-wise independence). A random variable Z ∈ {−1, 1}n is ε-almost d-wise
independent if, for any restriction of Z to d coordinates, the marginal distribution has statistical distance
at most ε from the uniform distribution on {−1, 1}d .
Naor and Naor [16] gave an explicit construction of an ε-almost d-wise random variable Z ∈ {−1, 1}n
with seed length O(log log n + d + log(1/ε)). We note that this seed length is optimal, up to the hidden
constants.
Lemma 4.4. Fix n, a, b ≥ 1 and ε > 0. There exists a fractional PRG X ∈ [−1, 1]n that fools Ln1 (a, b)
with error ε, such that
(i) X is p-noticeable for p = 1/(4b2 ).
(ii) The seed length of X is O(log log n + log(a/ε)).
Proof. Fix f ∈ Ln1 (a, b). Set d = dlog 2a/εe, δ = ε/2a, β = 1/2b. Let Z ∈ {−1, 1}n be a δ -almost
d-wise independent random variable, and set X = β Z which takes values in {−β , β }n . We claim that X
satisfies the requirements of the lemma. Claim (i) clearly holds, and claim (ii) holds by the Naor-Naor
construction. We thus focus on proving that X fools F with error ε.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 14
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
Fix f ∈ F and consider its Fourier expansion:
f (x) = ∑ fb(S)xS .
S⊆[n]
We need to show that E[ f (X)] is close to f (0). Averaging over X gives
|E[ f (X)] − f (0)| ≤ ∑ | fb(S)| · |E[X S ]| = ∑ | fb(S)| · β |S| |E[Z S ]|.
|S|>0 |S|>0
We next bound |E[Z S ]|. If |S| ≤ d then by the definition of Z we have |E[Z S ]| ≤ δ . If |S| > d we bound
trivially |E[Z S ]| ≤ 1. Let Wk = ∑S:|S|=k | fˆ(S)|, where by assumption Wk ≤ a · bk . Thus
d d
|E[ f (X)] − f (0)| ≤ δ ∑ Wk β k + ∑ Wk β k ≤ δ a ∑ (β b)k + a ∑ (β b)k ≤ δ a + 2−d a
k=1 k>d k=1 k>d
where we used the choice of β = 1/2b. The claim follows as we set δ = ε/2a and 2−d ≤ ε/2a.
Applying Theorem 2.5 using the fractional PRG constructed in Lemma 4.4 gives the following PRG
construction. Note that we still need to require that F is closed under restrictions.
Theorem 4.5. Let F be a family of n-variate Boolean functions closed under restrictions. Assume
that F ⊂ Ln1 (a, b) or that F ⊂ Ln2 (a, b). Then, for any ε ≤ 1/poly(b log n) there exists an explicit PRG
X ∈ {−1, 1}n which fools F with error ε > 0, whose seed length is O(log(n/ε)(log log n + log(a/ε))b2 ).
4.1 Applications
We apply our PRG from Theorem 4.5 to several well studied classes of Boolean functions that are known
to satisfy a Fourier tail bound.
4.1.1 Functions of bounded sensitivity
Let f : {−1, 1}n → {−1, 1} be a Boolean function. Its sensitivity at an input x ∈ {−1, 1}n is the number
of neighbors x0 of x (that is, x0 and x differ at exactly one coordinate) such that f (x0 ) 6= f (x). The (max)
sensitivity of f is s( f ) = maxx s( f , x). The sensitivity conjecture speculates that functions of sensitivity
s can be computed by decision trees of depth poly(s). A corollary would be that almost poly(s)-wise
distributions fool functions of low sensitivity. So, one may ask to construct comparable PRGs for
functions of low sensitivity.
This question was first considered by Hatami and Tal [10]. They constructed a PRG with subexpo-
√
nential seed length exp(O( s)). Theorem 4.5 gives an improved construction that essentially matches
the consequence of the sensitivity conjecture. Our PRG uses the recent bounds of Gopalan et al. [9] on
the Fourier tail of functions of low sensitivity. Concretely, Gopalan et al. [9] show that if s( f ) = s then
f ∈ L1 (1,t) for t = O(s). It is straightforward to verify that a restriction can only decrease the sensitivity
of the function, so that the class of functions of sensitivity at most s is closed under restrictions. A direct
application of Theorem 4.5 gives a PRG with seed length O(s2 log(n/ε)(log log(n) + log(1/ε))).
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 15
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
To get a somewhat improved bound, one can apply a result of Simon [21] that shows that if s( f ) = s
then f depends on at most m = 2O(s) many inputs. In this case, the analysis of Theorem 2.5 can be
applied with m variables instead of n variables , so that we only need O(log m/ε) iterations. Note that the
fractional PRG still requires a seed length which depends on the original n. We obtain:
Corollary 4.6. For any n, s ≥ 1 and ε ≤ 1/ poly(s), there exists an explicit PRG which fools n-variate
Boolean functions with sensitivity s with error ε, whose seed length is
O s3 log 1/ε)(log log n + log(1/ε)) .
We note that the log log n term cannot be removed. Indeed, even if we restrict attention to functions
which are XOR of at most 2 bits (for which s = 2) the seed length required is Ω(log log n + log(1/ε)).
4.1.2 Unordered branching programs
An oblivious read-once branching program (abbrv ROBP) B of width w is a non-uniform model of
computation, that captures randomized algorithms with space log w. A branching program B maintains
a state in the set {1, . . . , w} and reads the input bits in a known fixed order. At time step i = 1, . . . , n, B
reads a bit and based on the time step, the read bit and the current state it transitions to a new state. Thus,
B can be thought of as a layered directed graph, with w nodes in each layer, and two edges going out of
each node to the immediately next layer, one labeled with a 1 and the other labeled with a −1.
Let Bn (w) be the class of n-variate Boolean functions computed by read-once oblivious branching
programs of width w, where the order of the inputs is arbitrary. A recent work of Chattopadhyay et
al. [6] showed that these functions have L1 bounded Fourier tails. Concretely, Bn (w) ⊂ Ln1 (1,t) for
t = O((log n)w ). They used this to construct a PRG with seed length O(log n)w−1 log2 (n/ε) log log n.
Using our PRG from Theorem 4.5 we get a comparable (although slightly worse) seed length. Note that
Bn (w) is closed under restrictions.
Corollary 4.7. Fix n, w ≥ 1 and ε ≤ 1/(log n)O(w) . There is an explicit PRG which fools Bn (w) with
error ε > 0, whose seed length is O(log(n/ε)(log log n + log 1/ε)(log n)2w ).
4.1.3 Permutation branching programs
A special case of read-once branching programs are permutation branching programs, where the transition
function from level i to level i + 1 in the graph is a permutation for every choice of the input bit. We
denote it by Bnperm (w) ⊂ Bn (w). Reingold et al. [20] showed that if a Boolean function is computed
by a permutation branching program of width w, then it has L2 bounded Fourier tails with parameter
2w2 . Note that permutation branching programs are also closed under restrictions. Thus we obtain the
following result:
Corollary 4.8. Fix n, w ≥ 1 and ε ≤ 1/(poly(w, log n)). There is an explicit PRG which fools Bnperm (w)
with error ε > 0, whose seed length is O(log(n/ε)(log log n + log 1/ε)w4 ).
The dependence on n in our PRG is better than the result of Reingold et al. [20], as they obtained
seed length O(w2 log(w) log(n) log(nw/ε) + w4 log2 (w/ε)).
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 16
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
Reingold et al. [20] actually show the Fourier tail bounds for a more general class of branching
programs, called regular branching programs. However, these are not closed under restriction, and hence
our PRG construction fails to work (the same problem occurs also in the construction from [20]).
4.1.4 Bounded-depth circuits
The class of bounded-depth Boolean circuits AC0 has been widely studied. In particular, Linial, Mansour
and Nisan [12] showed that it has bounded L2 Fourier tails. Tal [22] obtained improved bounds. If f
is an n-variate Boolean function computed by an AC0 circuit of depth d and size s, then f ∈ L2 (n,t)
for t = 2O(d) logd−1 s. Theorem 4.5 provides a new PRG for AC0 which is comparable with the existing
PRGs of Nisan [17], Braverman [4], Tal [22], and Trevisan and Xue [23].
Corollary 4.9. Fix n, s ≥ 1 and ε ≤ 1/(log s)O(d) (log n)O(1) . There is an explicit PRG which fools n-
variate functions which can be computed by AC0 circuits of size s and depth d, with error ε > 0, whose
seed length is O(log(n/ε)(log log n + log 1/ε) log2d−2 s).
5 PRG for functions which simplify under random restriction
Another generic application of our framework is constructing PRGs for classes that simplify under random
restriction. Let F be a family of functions f : {−1, 1}n → {−1, 1} which are extended multilinearly to
[−1, 1]n . Fix a parameter 0 < p < 1 and define the p-averaged function of f , denoted f p : {−1, 1}n →
[−1, 1] as follows: sample A ⊆ [n] where Pr[i ∈ A] = p independently for i ∈ [n], and define
f p (x) = EA EU [ f (xA ,UAc )]
where xA ∈ {−1, 1}A is the restriction of the input x to the coordinates in A, and U ∈ {−1, 1}n is
independently and uniformly chosen.
Claim 5.1. f p (x) = f (px).
Proof. Let A,U be random variables as defined above. Define a random variable Y ∈ {−1, 1}n as follows:
(
xi if Ai = 1,
Yi =
Ui if Ai = 0.
Note that Y is a product distribution. By definition of f p , f p (x) = E[ f (Y )]. By multilinearity of f ,
E[ f (Y )] = f (E[Y ]) = f (px).
Overall, using Claim 5.1, we obtain the following corollary of Theorem 2.5.
Corollary 5.2. Suppose that we have a standard PRG X for the class of p-averaged functions F p = { f p :
f ∈ F} with error ε. Then X 0 = pX is a fractional PRG for the class F. Therefore, we get a standard
PRG for F using t = O(log(n/ε)/p2 ) independent copies of X that has error tε.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 17
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
6 Spectral tail bounds for low-degree F2 -polynomials
In this section, we prove L1 Fourier tail bounds for functions computed by low-degree polynomials on
F2 . However, our bounds fall short of implying PRGs for the class of low-degree F2 polynomials in our
framework.
Theorem 6.1. Let p : Fn2 → F2 be a polynomial of degree d, and let f (x) = (−1) p(x) . Then
∑ | fb(S)| ≤ (k23d )k ∀k = 1, . . . , n.
S⊆[n]
|S|=k
We note that L2 bounds do not hold for low-degree polynomials, as can be witnessed by taking a
high-rank quadratic polynomial. We prove Theorem 6.1 in the remainder of this section. For convenience,
with a slight abuse of notation, we use the basis f : {−1, 1} → {−1, 1}. We first introduce some notation
to simplify the presentation. Let
Wk ( f ) := ∑ | fˆ(S)|
|S|=k
denote the weight of the level-k Fourier coefficients of a Boolean function f , and let
W (d, k) := max{Wk ( f ) : f = (−1) p , deg(p) ≤ d}
be the maximum of Wk over degree-d polynomials. Note that we do not make any assumption on the
number of variables n. We prove the following lemma from which Theorem 6.1 follows relatively easily.
Lemma 6.2. For any d, k ≥ 1,
k
k
W (d, k)2 ≤ 22kW (d − 1, 2k) +W (d, k) · ∑ W (d, k − `).
`=1 `
We first show that Theorem 6.1 follows easily from Lemma 6.2.
Proof of Theorem 6.1 given Lemma 6.2. The proof of Theorem 6.1 is by induction, first on d and then
on k. The base case of d = 1 is straightforward, so assume d ≥ 2. By Lemma 6.2 we have
2k k k−`
2 2k
3(d−1) k
W (d, k) ≤ 2 2k · 2 +W (d, k) ∑ (k − `)23d
`=1 `
2k k k−`
3d−1 k
≤ k·2 +W (d, k) ∑ (k − 1)23d
`=1 `
2k k k
3d−1 3d 3d
= k·2 +W (d, k) (k − 1)2 + 1 − (k − 1)2 .
Assume towards a contradiction that W (d, k) > (k23d )k . Dividing by W (d, k) on both sides gives
k k k
W (d, k) ≤ k · 23d−1 + (k − 1)23d + 1 − (k − 1)23d .
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 18
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
If k = 1 then we reach a contradiction as 23d−1 + 1 ≤ 23d . If k > 1 then as (k − 1)23d ≥ k23d−1 the first
term gets canceled by the third term, and the second term is at most (k23d )k . In either case, we reached a
contradiction.
From now on we focus on proving Lemma 6.2. To that end, fix f computed by a polynomial of degree
d which maximizes Wk ( f ). We shorthand g(S) = | fˆ(S)|. The following claims are used in the proof of
Lemma 6.2.
Claim 6.3. For any 0 ≤ a < b ≤ n and A ⊂ [n] of size |A| = a,
∑ g(B) ≤ W (d, b − a).
B:|B|=b,A⊆B
Claim 6.4. ∑ g(S)g(T ) ≤ 22kW (d − 1, 2k).
S,T :|S|=|T |=k,S∩T =0/
Claim 6.5. For any 1 ≤ ` ≤ k,
k
∑ g(S)g(T ) ≤ W (d, k)W (d, k − `).
S,T :|S|=|T |=k,|S∩T |=`
`
We first show how to prove Lemma 6.2 using the above claims.
Proof of Lemma 6.2. We have,
W (d, k)2 = ∑ g(S)g(T )
S,T :|S|=|T |=k
k
=∑ ∑ g(S)g(T )
`=0 S,T :|S|=|T |=k,|S∩T |=`
k
= ∑ g(S)g(T ) + ∑ ∑ g(S)g(T )
S,T :|S|=|T |=k,S∩T =0/ `=1 S,T :|S|=|T |=k,|S∩T |=`
k
2k k
≤ 2 W (d − 1, 2k) +W (d, k) · ∑ W (d, k − `),
`=1 `
where the last inequality follows by using the bounds from Claim 6.4 and Claim 6.5.
We now proceed to prove the missing claims.
Proof of Claim 6.3. We use induction on a and b. The claim is direct for a = 0 and any b > a. Thus
suppose b > a > 0 and let i ∈ A. Let A0 = A \ {i}. We have
∑ g(B) = ∑ g(B0 ∪ {i})
B:|B|=k,A⊆B B0 ⊆[n]\{i}:|B0 |=b−1,A0 ⊆B0
= ∑ | fb(B0 ∪ {i})|.
B0 ⊆[n]\{i}:|B0 |=b−1,A0 ⊆B0
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 19
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Let fi→1 and fi→−1 be the functions obtained from f by setting the i’th bit to 1 and −1, respectively. It is
easy to verify that | fb(B ∪ {i})| = 21 | fd
i→1 (B) − \
fi→−1 (B)|. Thus, continuing with our estimate, we have
1 0
fi→−1 (B0 )|
∑ g(B) ≤ ∑ | fd
i→1 (B )| + |\
B:|B|=b,A⊆B
2 B0 :|B0 |=b−1,A0 ⊆B0 ∪{i}
≤ W (d, (b − 1) − (a − 1)) = W (d, b − a),
where the last inequality follows from induction hypothesis.
Proof of Claim 6.4. For any S ⊆ [n], let eS ∈ {−1, 1} be the sign of fb(S), so that g(S) = eS · fb(S). Let
X,Y, Z be independent uniform distributions on {−1, 1}n . We have
∑ g(S)g(T ) = ∑ eS eT EY [ f (Y )Y S ] · EZ [ f (Z)Z T ]
S,T :|S|=|T |=k,S∩T =0/ S,T :|S|=|T |=k,S∩T =0/
= ∑ eS eT EY,Z [ f (Y )Y S f (Z)Z T ]
S,T :|S|=|T |=k,S∩T =0/
= ∑ eS eT EX,Y,Z [ f (X ◦Y ) f (X ◦ Z)X S∪T Y S Z T ].
S,T :|S|=|T |=k,S∩T =0/
This follows as (Y, Z) and (X ◦Y, X ◦ Z) are identically distributed. Now consider any fixing of Y = y
and Z = z. Define the function hy,z (x) = f (x ◦ y) f (x ◦ z). Recall that f is a degree-d polynomial. Thus
hy,z (x) = f (x) f (x ◦ z ◦ y) is the multiplicative derivative of f in direction y ◦ z. In particular, the degree
of hy,z is at most d − 1, since taking derivatives always reduces the degree. More information about
properties of derivatives can be found in [19]. Thus we have
S T S∪T 2k
∑ eS eT y z E[ f (X ◦ y) f (X ◦ z)X ] ≤
k ∑ E[hy,z (X)X R ]
S,T :|S|=|T |=k,S∩T =0/ R:|R|=2k
≤ 22kW (d − 1, 2k).
The proof follows now by noting that the above bound holds for any choice of y and z, and then averaging
over y = Y, z = Z.
Proof of Claim 6.5. We have,
2
∑ g(S)g(T ) ≤ ∑ ∑ g(S)
S,T :|S|=|T |=k,|S∩T |=` L:|L|=` S:|S|=k,L⊆S
≤ max ∑ g(S) ∑ g(S)
L:|L|=` S:|S|=k,L⊆S L,S:|L|=`,|S|=k,L⊆S
≤ W (d, k − `) · ∑ ∑ g(S) (using Claim 6.3)
S:|S|=k L:L⊆S,|L|=`
k
≤ W (d, k − `) · ·W (d, k).
`
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 20
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
7 Smoothness
In this section we provide a partial answer for Open Problem 1.5, regarding early termination of the
random walk. Let Yt ∈ [−1, 1]n be the location of the random walk at time t. We would like to guarantee
that if Yt is close enough to sign(Yt ) then we can round Yt to sign(Yt ) without changing the value of f by
too much. Therefore, given f : [−1, 1]n → [−1, 1], it would be desirable to show f is “smooth” enough:
there is a bound W such that
∀α, β ∈ [−1, 1]n , | f (α) − f (β )| ≤ W kα − β k∞ .
Observe that should such a W exist, then if at some step t we have kYt − sign(Yt )k∞ ≤ ε/W , then we can
terminate the random walk immediately and guarantee that k f (Yt ) − f (sign(Yt ))k∞ ≤ ε. We show that
such smoothness property holds for functions with bounded sensitivity.
7.1 Bounded sensitivity functions
We show that smoothness follows from a bound on the (maximum) sensitivity of a Boolean function.
Lemma 7.1. Let f : {−1, 1}n → [−1, 1] be a boolean function with maximum sensitivity s. Then, for any
α, β ∈ [−1, 1]n it holds that
| f (α) − f (β )| ≤ 8skα − β k∞ .
We first consider the case that kα − β k∞ is very small.
Claim 7.2. Let f : {−1, 1}n → [−1, 1] be a Boolean function with maximum sensitivity s. Let α, β ∈
[−1, 1]n such that kα − β k∞ ≤ 1/n2 . Then
| f (α) − f (β )| ≤ 8skα − β k∞ .
To prove the result for arbitrary α, β ∈ [−1, 1]n using Claim 7.2, consider the line segment from α to
β and integrate f along that line segment. Thus, Lemma 7.1 follows directly from Claim 7.2.
Proof of Claim 7.2. Let δ = kα − β k∞ . We first consider the easier case of α ∈ {−1, 1}n . Pick b ∈
{−1, 1}n randomly by flipping each coordinate of α independently with probability |αi − βi |/2 so that
E f (b) = f (β ). Note that f (b) 6= f (α) if either exactly one sensitive coordinate of α is flipped, which
occurs with probability at most sδ , or if at least two coordinates get flipped, which occurs with probability
at most (nδ )2 . Therefore
| f (α) − E f (b)| ≤ sδ + n2 δ 2 ≤ 2sδ
given our assumption on δ .
Next, consider the general case of α ∈ [−1, 1]n . This case requires introducing an extra point
γ ∈ [−1, 1]n in a way that allows us to prove
| f (α) − f (γ)| ≤ 4s · kα − γk∞ (7.1)
and
| f (β ) − f (γ)| ≤ 4s · kβ − γk∞ (7.2)
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 21
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
separately. We choose γ in a way that ∀i ∈ [n], γi = αi or γi = βi . These equations altogether give the
claim. To choose γ, let S ⊆ [n] be the set of coordinates that |αi | < |βi | and pick γi = αi if i ∈ S, and
γi = βi otherwise.
We next prove Equation (7.1). The proof of Equation (7.2) is analogous. Consider a joint random
variable (a, c) that satisfies the following properties:
1. a ∈ {−1, 1}n , c ∈ [−1, 1]n , Ea = α, and Ec = γ.
2. The marginal distributions of a and c are product distributions.
3. ka − Ec [c|a]k∞ ≤ 2kα − γk∞ holds with probability one.
Observe that given such (a, c),
| f (α) − f (γ)| = |Ea,c [ f (a) − f (c)]| ≤ Ea | f (a) − Ec [ f (c)|a]| ≤ 4s · kα − γk∞ ,
where the last inequality uses the first case in the proof, as a ∈ {−1, 1}n .
Now let us construct the joint random variable (a, c). Fix i ∈ [n] and suppose without loss of generality
that αi ≥ 0. Note that by construction −αi ≤ γi ≤ αi . First sample ai so that E[ai ] = αi . If ai = −1 then
set ci = −1, otherwise set
2γi + 1 − αi
ci = .
1 + αi
It’s easy to check that this choice of (a, c) satisfies the required conditions, finishing the proof.
Acknowledgments
We thank Avi Wigderson and David Zuckerman for various stimulating discussions during the course of
our work.
References
[1] M IKLÓS A JTAI AND AVI W IGDERSON: Deterministic simulation of probabilistic constant depth
circuits. Advances in Computing Research, 5:199–222, 1989. Preliminary version in FOCS’85. 6
[2] N OGA A LON , O DED G OLDREICH , J OHAN H ÅSTAD , AND R ENÉ P ERALTA: Simple constructions
of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304,
1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308] 2
[3] N IKHIL BANSAL: Constructive algorithms for discrepancy minimization. In Proc. 51st FOCS, pp.
3–10. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.7, arXiv:1002.2259] 7
[4] M ARK B RAVERMAN: Polylogarithmic independence fools AC0 circuits. J. ACM, 57(5):28, 2010.
Preliminary version in CCC’09. [doi:10.1145/1754399.1754401] 17
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 22
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
[5] E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT: Pseu-
dorandom generators from polarizing random walks. In Proc. 33rd Computational Complexity Conf.
(CCC’18), pp. 1:1–1:21. Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2018.1]
1
[6] E SHAN C HATTOPADHYAY, P OOYA H ATAMI , O MER R EINGOLD , AND AVISHAY TAL: Improved
pseudorandomness for unordered branching programs through local monotonicity. In Proc. 50th
STOC, pp. 363–375. ACM Press, 2018. [doi:10.1145/3188745.3188800] 5, 6, 14, 16
[7] O DED G OLDREICH: A Primer on Pseudorandom Generators. Volume 55 of Univ. Lecture Ser.
Amer. Math. Soc., 2010. author’s home page. 2
[8] PARIKSHIT G OPALAN , R AGHU M EKA , O MER R EINGOLD , L UCA T REVISAN , AND S ALIL VAD -
HAN: Better pseudorandom generators from milder pseudorandom restrictions. In Proc. 53rd FOCS,
pp. 120–129. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.77, arXiv:1210.0049] 6, 7
[9] PARIKSHIT G OPALAN , ROCCO A S ERVEDIO , AND AVI W IGDERSON: Degree and sensitivity:
tails of two distributions. In Proc. 31st Computational Complexity Conf. (CCC’16), pp. 13:1–13:23.
Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.13,
arXiv:1604.07432] 14, 15
[10] P OOYA H ATAMI AND AVISHAY TAL: Pseudorandom generators for low sensitivity functions. In
Proc. 9th Innovations in Theoretical Computer Sci. Conf. (ITCS’18), pp. 29:1–29:13. Leibniz-
Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.29] 5, 6, 15
[11] S HLOMO H OORY, NATHAN L INIAL , AND AVI W IGDERSON: Expander graphs and their appli-
cations. Bull. Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]
2
[12] NATHAN L INIAL , Y ISHAY M ANSOUR , AND N OAM N ISAN: Constant depth circuits, Fourier
transform, and learnability. J. ACM, 40(3):607–620, 1993. Preliminary version in FOCS’89.
[doi:10.1145/174130.174138] 14, 17
[13] S HACHAR L OVETT AND R AGHU M EKA: Constructive discrepancy minimization by walking
on the edges. SIAM J. Comput., 44(5):1573–1582, 2015. Preliminary version in FOCS’12.
[doi:10.1137/130929400, arXiv:1203.5747] 7
[14] S HACHAR L OVETT, AVISHAY TAL , AND J IAPENG Z HANG: The robust sensitivity of Boolean
functions. In Proc. 29th ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1822–1833.
SIAM, 2018. [doi:10.1137/1.9781611975031.119] 14
[15] Y ISHAY M ANSOUR: An nO(log log n) learning algorithm for DNF under the uniform distri-
bution. J. Comput. System Sci., 50(3):543–550, 1995. Preliminary version in COLT’92.
[doi:10.1006/jcss.1995.1043] 14
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 23
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
[16] J OSEPH NAOR AND M ONI NAOR: Small-bias probability spaces: Efficient constructions and
applications. SIAM J. Comput., 22(4):838–856, 1993. Preliminary version in STOC’90.
[doi:10.1137/0222053] 2, 14
[17] N OAM N ISAN: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991.
[doi:10.1007/BF01375474] 17
[18] N OAM N ISAN AND AVI W IGDERSON: Hardness vs randomness. J. Comput. System Sci., 49(2):149–
167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1] 2
[19] RYAN O’D ONNELL: Analysis of Boolean Functions. Cambridge Univ. Press, 2014.
[doi:10.1017/CBO9781139814782] 20
[20] O MER R EINGOLD , T HOMAS S TEINKE , AND S ALIL VADHAN: Pseudorandomness for regu-
lar branching programs via Fourier analysis. In Proc. Internat. Workshop on Approximation,
Randomization, and Combinatorial Optimization (RANDOM’13), pp. 655–670. Springer, 2013.
[doi:10.1007/978-3-642-40328-6_45, arXiv:1306.3004] 5, 6, 14, 16, 17
[21] H ANS -U LRICH S IMON: A tight Ω(log log n)-bound on the time for parallel RAM’s to compute
nondegenerated Boolean functions. Inf. Control, 55(1–3):102–107, 1982. See also FCT’83.
[doi:10.1016/S0019-9958(82)90477-6] 16
[22] AVISHAY TAL: Tight bounds on the Fourier spectrum of AC0 . In Proc. 32nd Computa-
tional Complexity Conf. (CCC’17), pp. 15:1–15:31. Leibniz-Zentrum fuer Informatik, 2017.
[doi:10.4230/LIPIcs.CCC.2017.15] 5, 14, 17
[23] L UCA T REVISAN AND T ONGKE X UE: A derandomized switching lemma and an improved
derandomization of AC0 . In Proc. 28th IEEE Conf. on Computational Complexity (CCC’13), pp.
242–247. IEEE Comp. Soc. Press, 2013. [doi:10.1109/CCC.2013.32] 6, 17
[24] S ALIL VADHAN: Pseudorandomness. Foundations and Trends in Theoret. Computer Sci., 7(1–3):1–
336, Now Publ., 2012. [doi:10.1561/0400000010] 2
[25] E MANUELE V IOLA: The sum of D small-bias generators fools polynomials of degree D. Comput.
Complexity, 18(2):209–217, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0273-
5] 6
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 24
P SEUDORANDOM G ENERATORS FROM P OLARIZING R ANDOM WALKS
AUTHORS
Eshan Chattopadhyay
Assistant professor
Department of Computer Science
Cornell University
Ithaca, New York, USA
eshan cs cornell edu
https://www.cs.cornell.edu/~eshan/
Pooya Hatami
Postdoctoral researcher
University of Texas, Austin
Texas, USA
pooyahat gmail com
https://pooyahatami.org/
Kaave Hosseini
Ph. D. candidate
University of California, San Diego
California, USA
skhossei ucsd edu
http://cseweb.ucsd.edu/~skhossei/
Shachar Lovett
Associate professor
University of California, San Diego
California, USA
slovett ucsd edu
http://cseweb.ucsd.edu/~slovett/
ABOUT THE AUTHORS
E SHAN C HATTOPADHYAY received his Ph. D. from UT Austin in 2016 under the supervision
of David Zuckerman. He was a postdoctoral researcher at the Institute for Advanced
Study, Princeton and the Simons Institute for Theory of Computing till 2018. Since
2018, he has been a faculty at Cornell University. His research interests lie primarily in
pseudorandomness and its applications to complexity theory, cryptography, and coding
theory. His hobbies include traveling and playing cricket.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 25
E SHAN C HATTOPADHYAY, P OOYA H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
P OOYA H ATAMI is a postdoctoral researcher at UT Austin hosted by David Zuckerman. He
received his Ph. D. from the University of Chicago in 2015 under the supervision of
Alexander Razborov and Madhur Tulsiani. He has also spent two years as a postdoctoral
researcher at the Institute for Advanced Study at Princeton and DIMACS at Rutgers
University. His research interests lie broadly in theoretical computer science, particularly
the role of pseudorandomness and randomness in computational complexity. He spends
most of his spare time climbing rocks and plastic.
K AAVE H OSSEINI is a Ph. D. candidate at UC San Diego under the supervision of Shachar
Lovett. He obtained his undergraduate degree in mathematics and computer science at
Sharif University of Technoogy, Iran. His research interests lie in additive combinatorics
and computational complexity. He is mostly interested in approximate algebraic struc-
tures, the structure vs. randomness dichotomy, and pseudorandomness. He likes world
music and plays Djembe (a West African drum), and also thinks he is still young enough
to be a good gymnast.
S HACHAR L OVETT received his Ph. D. from the Weizmann Institute of Science in 2010
under the supervision of Omer Reingold and Ran Raz. He was a postdoctoral researcher
at the Institute for Advanced Study until 2012. Since 2012, he has been a faculty at the
University of California, San Diego. He is a recipient of an NSF CAREER award and a
Sloan fellowship. His research is broadly in theoretical computer science and combina-
torics. In particular: computational complexity, randomness and pseudo-randomness,
algebraic constructions, coding theory, additive combinatorics and combinatorial aspects
of high-dimensional geometry. He is happily married and has three kids.
T HEORY OF C OMPUTING, Volume 15 (10), 2019, pp. 1–26 26