Pseudorandomness via the discrete Fourier transform

Introduction

A central goal of computational complexity is to understand the power that randomness adds to efficient computation. The main questions in this area are whether ${\mathsf{BPP}}={\mathsf{P}}$ and ${\mathsf{RL}}={\mathsf{L}}$, which respectively assert that randomness can be eliminated from efficient computation, at the price of a polynomial slowdown in time, and a constant blowup in space. It is known that proving ${\mathsf{BPP}}={\mathsf{P}}$ will imply strong circuit lower bounds that seem out of reach of current techniques. In contrast, proving ${\mathsf{RL}}={\mathsf{L}}$, could well be within reach. Indeed, bounded-space algorithms are a natural computational model for which we know how to construct strong pseudo-random generators, ${\mathsf{PRG}}$s, unconditionally.

Let ${\mathsf{RL}}$ denote the class of randomized algorithms with $O(\log n)$ work space which can access the random bits in a read-once pre-specified order. Nisan [Nis92] devised a ${\mathsf{PRG}}$ of seed length $O(\log^{2}(n/\varepsilon))$ that fools ${\mathsf{RL}}$ with error $\varepsilon$. This generator was subsequently used by Nisan [Nis94] to show that ${\mathsf{RL}}\subseteq\mathsf{SC}$ and by Saks and Zhou [SZ99] to prove that ${\mathsf{RL}}$ can be simulated in space $O(\log^{3/2}n)$. Constructing ${\mathsf{PRG}}$s with the optimal $O(\log(n/\varepsilon))$ seed length for this class and showing that ${\mathsf{RL}}={\mathsf{L}}$ is arguably the outstanding open problem in derandomization (which might not require a breakthrough in lower bounds). Despite much progress in this area [INW94, NZ96, RR99, Rei08, RTV06, BRRY14, BV10, KNP11, De11, GMR+12], there are few cases where we can improve on Nisan’s twenty year old bound of $O(\log^{2}(n/\varepsilon))$ [Nis92].

We motivate the problem of constructing ${\mathsf{PRG}}$s for Fourier shapes by discussing how they capture a variety of well-studied classes like halfspaces (over general domains), combinatorial rectangles, modular tests and combinatorial shapes.

Halfspaces are functions $h:\{0,1\}^{n}\to\{0,1\}$ that can be represented as

We show that a ${\mathsf{PRG}}$ for $(2,n)$-Fourier shapes with error $\varepsilon/n^{2}$ also fools halfspaces with error $\varepsilon$. In particular, ${\mathsf{PRG}}$s fooling Fourier shapes with polynomially small error also fool halfspaces with small error.

${\mathsf{PRG}}$s for $(m,n)$-Fourier shapes give us ${\mathsf{PRG}}$s for halfspaces not just for the uniform distribution over the hypercube, but for a large class of distributions that have been studied in the literature. We can derive these results in a unified manner by considering the class of generalized halfspaces.

A generalized halfspace over $[m]^{n}$ is a function $g:[m]^{n}\to\{0,1\}$ that can be represented as

A consequence of fooling generalized halfspaces is to derandomize Chernoff-Hoeffding type bounds for sums of independent random variables which are ubiquitous in the analysis of randomized algorithms. We state our result in the language of “randomness-efficient samplers” (cf. [Zuc97]). Let $X_{1},\ldots,X_{n}$ be independent random variables over a domain $[m]$ and let $g_{1},\ldots,g_{n}:[m]\to$ be arbitrary bounded functions. The classical Chernoff-Hoeffding bounds [Hoe63] say that

Combinatorial shapes were introduced in the work of [GMRZ13] as a generalization of combinatorial rectangles and to address fooling linear sums in statistical distance. These are functions $f:[m]^{n}\to\{0,1\}$ of the form

for functions $g_{i}:[m]\to\{0,1\}$ and a function $h:\{0,\ldots,n\}\to\{0,1\}$. The best previous generators of [GMRZ13] and [De14] for combinatorial shapes achieve a seed-length of $O(\log(mn)+\log^{2}(1/\varepsilon))$, $O(\log m+\log(n/\varepsilon)^{3/2})$; in particular, the best previous seed-length for polynomially small error was $O(\log^{3/2}(n))$. ${\mathsf{PRG}}$s for $(m,n)$-Fourier shapes with error $\varepsilon/n$ imply ${\mathsf{PRG}}$s for combinatorial shapes.

Combinatorial rectangles are a well-studied subset of combinatorial shapes [EGL+98, ASWZ96, LLSZ97, Lu02]. They are functions that can be written as $f(x)=\prod_{j}\mathds{1}(x_{j}\in A_{j})$ for some arbitrary subsets $A_{j}\subseteq[m]$. The best known ${\mathsf{PRG}}$ due to [GMR+12, GY14] gives a seed-length of $O(\log(mn/\varepsilon)\log\log(mn/\varepsilon))$. Combinatorial rectangles are special cases of Fourier shapes so our ${\mathsf{PRG}}$ for $(m,n)$-Fourier shapes also fools combinatorial rectangles, but requires a slightly longer seed. The alphabet-reduction step in our construction is inspired by the generator of [GMR+12, GY14].

1.2 Achieving optimal error dependence via Fourier shapes.

We briefly explain why previous techniques based on limit theorems were unable to achieve polynomially small error with optimal seed-length, by considering the setting of halfspaces under the uniform distribution on $\{0,1\}^{n}$. Fooling halfspaces is equivalent to fooling all linear functions $L(x)=\sum_{i}w_{i}x_{i}$ in Kolmogorov or cdf distance. Previous work on fooling halfspaces [DGJ+09, MZ13] relies on the Berry-Esséen theorem, a quantiative form of the central limit theorem, to show that the cdf of regular linear functions is close to that of the Gaussian distribution, both under the uniform distribution and under the pseudorandom distribution. However, even for the majority function (which is the most regular linear function), the discreteness of $\sum_{i}x_{i}$ means that the Kolmogorov distance from the Gaussian distribution is $1/\sqrt{n}$, even when $x$ is uniformly random. Approaches that show closeness in cdf distance by comparison to the Gaussian distribution seem unlikely to give polynomially small error with optimal seed-length.

We depart from the derandomized limit theorem approach taken by several previous works [DGJ+09, DKN10, GOWZ10, HKM12, GMRZ13, MZ13] and work directly with the Fourier transform. A crucial insight (that is formalized in Lemma 9.2) is that fooling the Fourier transform of linear forms to within polynomially small error implies polynomially small Kolmogorov distance.

2 Our results

There is an explicit generator $\mathcal{G}:\{0,1\}^{r}\to[m]^{n}$ that fools all $(m,n)$-Fourier shapes with error $\varepsilon$, and has seed-length $r=O(\log(mn/\varepsilon)\cdot(\log\log(mn/\varepsilon))^{2})$.

We now state various corollaries of our main result starting with fooling halfspaces.

There is an explicit generator $\mathcal{G}:\{0,1\}^{r}\to\{0,1\}^{n}$ that fools halfspaces over $\{0,1\}^{n}$ under the uniform distribution with error $\varepsilon$, and has seed-length $r=O(\log(n/\varepsilon)(\log\log(n/\varepsilon))^{2})$.

The best previous generator due to [MZ13] had a seed-length of $O(\log n+\log^{2}(1/\varepsilon))$, which is $O(\log^{2}n)$ for polynomially small error $\varepsilon$.

We also get a ${\mathsf{PRG}}$ with similar parameters for generalized halfspaces.

There is an explicit generator $\mathcal{G}:\{0,1\}^{r}\to[m]^{n}$ that $\varepsilon$-fools generalized halfspaces over $[m]^{n}$, and has seed-length $r=O(\log(mn/\varepsilon)\cdot(\log\log(mn/\varepsilon))^{2})$.

The generator $G$ has seed-length $r=O(\log(nC/\varepsilon)(\log\log(nC/\varepsilon))^{2})$.

This improves on the result of [GOWZ10] who obtained seedlength $O(\log(nC/\varepsilon)\log(C/\varepsilon)$ for this setting via a suitable modification of the generator from [MZ13].

The next corollary is a near-optimal derandomization of the Chernoff-Hoeffding bounds. To get a similar guarantee, the best known seed-length that follows from previous work [SSS95, MZ13, GOWZ10] was $O(\log(mn)+\log^{2}(1/\varepsilon))$.

Let $X_{1},\ldots,X_{n}$ be independent random variables over the domain $[m]$. Let $g_{1},\ldots,g_{n}:[m]\to$ be arbitrary bounded functions. There exists an explicit generator $G:\{0,1\}^{r}\to[m]^{n}$ such that if $(Y_{1},\ldots,Y_{n})=G(z)$ where $z\in_{u}\{0,1\}^{r}$, then $Y_{i}$ is distributed identically to $X_{i}$ and

$G$ has seed-length $r=O(\log(mn/\varepsilon)(\log\log(mn/\varepsilon))^{2})$.

There is an explicit generator $\mathcal{G}:\{0,1\}^{r}\to\{0,1\}^{n}$ that fools all linear tests modulo $m$ for all $m\leq M$ with error $\varepsilon$, and has seed-length $r=O(\log(Mn/\varepsilon)\cdot(\log\log(Mn/\varepsilon))^{2})$.

Finally, we get a generator with near-logarithmic seedlength for fooling combinatorial shapes. [GMRZ13] gave a ${\mathsf{PRG}}$ for combinatorial shapes with a seed-length of $O(\log(mn)+\log^{2}(1/\varepsilon))$. This was improved recently by De [De14] who gave a ${\mathsf{PRG}}$ with seed-length $O(\log m+\log(n/\varepsilon)^{3/2})$; in particular, the best previous seed-length for polynomially small error was $O((\log(n)^{3/2})$.

There is an explicit generator $\mathcal{G}:\{0,1\}^{r}\to[m]^{n}$ that fools $(m,n)$-combinatorial shapes to error $\varepsilon$ and has seed-length $r=O(\log(mn/\varepsilon)(\log\log(mn/\varepsilon))^{2})$.

3 Other related work

Starting with the work of Diakonikolas et al. [DGJ+09], there has been a lot of interest in constructing ${\mathsf{PRG}}$s for halfspaces and related classes such as intersections of halfspaces and polynomial threshold functions over the domain $\{\pm 1\}^{n}$ [DKN10, GOWZ10, HKM12, MZ13, Kan11b, Kan11a, Kan14]. Rabani and Shpilka [RS10] construct optimal hitting set generators for halfspaces over $\{\pm 1\}^{n}$; hitting set generators are weaker than ${\mathsf{PRG}}$s.

Another line of work gives ${\mathsf{PRG}}$s for halfspaces for the uniform distribution over the sphere (spherical caps) or the Gaussian distribution. For spherical caps, Karnin, Rabani and Shpilka [KRS12] gave a ${\mathsf{PRG}}$ with a seed-length of $O(\log n+\log^{2}(1/\varepsilon))$. For the Gaussian distribution, [Kan14] gave a ${\mathsf{PRG}}$ which achieves a seed-length of $O(\log n+\log^{3/2}(1/\varepsilon))$. Recently, [KM15] gave the first ${\mathsf{PRG}}$s for these settings with seedlength $O((\log(n/\varepsilon))(\log\log(n/\varepsilon)))$. Fooling halfspaces over the hypercube is known to be harder than the Gaussian setting or the uniform distribution on the sphere; hence our result gives a construction with similar parameters up to a $O(\log\log n)$ factor. At a high level, [KM15] also uses a iterative dimension reduction approach like in [KMN11, CRSW13, GMR+12]; however, the final construction and its analysis are significantly different from ours.

Gopalan et al. [GOWZ10] gave a generator fooling halfspaces under product distributions with bounded fourth moments, whose seed-length is $O(\log(n/\varepsilon)\log(1/\varepsilon))$.

The present work completely subsumes a manuscript of the authors which essentially solved the special-case of derandomizing Chernoff bounds and a special class of halfspaces [GKM14].

Proof overview

We describe our ${\mathsf{PRG}}$ for Fourier shapes as in Theorem 1.1. The various corollaries are derived from this Theorem using properties of the discrete Fourier transform of integer-valued random variables.

Let us first consider a very simple ${\mathsf{PRG}}$: $O(1)$-wise independent distributions over $[m]^{n}$. At a glance, it appears to do very poorly as it is easy to express the parity of a subset of bits as a Fourier shape and parities are not fooled even by $(n-1)$-wise independence. The starting point for our construction is that bounded independence does fool a special but important class of Fourier shapes, namely those with polynomially small total variance.

For a complex valued random variable $Z$, define the variance of $Z$ as

To gain some intuition for why this is a natural quantity, note that $\mathsf{Tvar}(f)$ gives an easy upper bound on the expectation of a Fourier shape:

To complement the above, we show that if the total-variance $\mathsf{Tvar}(f)$ is very small, then generators based on limited independence do fairly well. Concretely, our main technical lemma says that limited independence fools products of bounded (complex-valued) random variables, provided that the sum of their variances is small.

On the other hand, if $\mathsf{Tvar}(f)\leq 1/(mn)^{c}$ for a fixed constant $c$, then choosing $k=O(\log(1/\varepsilon)/(\log mn))$-wise independence is enough to get error $\varepsilon$ while also achieving seed-length $O(k\log(mn))=O(\log(1/\varepsilon))$ as desired. We exploit this observation by combining the use of limited independence with the recent iterative-dimension-reduction paradigm of [KMN11, CRSW13, GMR+12]. Our construction reduces the problem of fooling Fourier shapes with $\mathsf{Tvar}(f)\leq O(\log(1/\varepsilon))$ through a sequence of iterations to fooling Fourier shapes where the total variance is polynomially small in $m,n$ in each iteration and then uses limited independence in each iteration.

We construct a ${\mathsf{PRG}}$ with seed-length $O(\log(mn/\varepsilon)\log\log(1/\varepsilon))$ which $\varepsilon$-fools $(m,n)$-Fourier shapes $f$ when $\mathsf{Tvar}(f)\geq(\log(1/\varepsilon))^{C}$ for some sufficiently large constant $C$. We build the generator in two steps.

In the first step, we build a ${\mathsf{PRG}}$ with seed-length $O(\log(mn))$ which achieves constant error for $(m,n)$-Fourier shapes $f$ with $\mathsf{Tvar}(f)\geq 1$. In the second step, we drive the error down to $\varepsilon$ as follows. We hash the coordinates into roughly $(\log(1/\varepsilon))^{O(1)}$ buckets, so that for at least $\Omega(\log(1/\varepsilon))$ buckets, $f$ restricted to the coordinates within the bucket has total-variance at least $1$. We use the ${\mathsf{PRG}}$ with constant error within each bucket, while the seeds across buckets are recycled using a ${\mathsf{PRG}}$ for small-space algorithms. This construction is inspired by the construction of small-bias spaces due to Naor and Naor [NN93]; the difference being that we use generators for space bounded algorithms for amplification, as opposed to expander random walks as done in [NN93].

2 Alphabet-reduction

The next building block in our construction is alphabet-reduction which helps us assume without loss of generality that the alphabet-size $m$ is polynomially bounded in terms of the dimension $n$. This is motivated by the construction of [GMR+12].

Concretely, we show that constructing an $\varepsilon$-${\mathsf{PRG}}$ for $(m,n)$-Fourier shapes can be reduced to that of constructing an $\varepsilon^{\prime}$-${\mathsf{PRG}}$ for $(n^{4},n)$-Fourier shapes for $\varepsilon^{\prime}\approx\varepsilon/(\log m)$. The alphabet-reduction step consists of $(\log\log m)$ steps where in each step we reduce fooling $(m,n)$-Fourier shapes for $m>n^{4}$, to that of fooling $(\sqrt{m},n)$-Fourier shapes, at the cost of $O(\log(m/\varepsilon))$ random bits.

We now describe a single step that reduces the alphabet from $m$ to $\sqrt{m}$. Consider the following procedure for generating a uniformly random element in $[m]^{n}$:

For $D\approx\sqrt{m}$, sample uniformly random subsets

Sample $Y=(Y_{1},\ldots,Y_{n})$ uniformly at random from $[D]^{n}$.

Output $(Z_{1},\ldots,Z_{n})$, where $Z_{j}=X[Y_{j},j]$.

Our goal is to derandomize this procedure. The key observation is that once the subsets $S_{1},\ldots,S_{n}$ are chosen, we are left with a $(D,n)$-Fourier shape as a function of $Y$. So the choice of $Y$ can be derandomized using a ${\mathsf{PRG}}$ for Fourier shapes with alphabet $[D]$, and it suffices to derandomize the choice of the $X$’s. A calculation shows that (because the $Y$’s are uniformly random), derandomizing the choice of the $X$’s reduces to that of fooling a Fourier shape of total-variance $1/m^{\Omega(1)}$. Lemma 2.1 implies that this can be done with limited independence.

3 Dimension-reduction for low-variance Fourier shapes

We first hash the coordinates into roughly $\sqrt{n}$ buckets using a $k$-wise independent hash function $h\in_{u}\mathcal{H}=\{h:[n]\leftarrow[\sqrt{n}]\}$ for $k\approx O(\log(n/\varepsilon)/\log n)$. Note that this only requires $O(\log(n/\varepsilon))$ random bits.

For the coordinates within each bucket we use a $k^{\prime}$-wise independent string in $[m]^{n}$ for $k^{\prime}\approx O(\log(n/\varepsilon)/\log n)$. We use true independence across buckets. Note that this requires $\sqrt{n}$ independent seeds of length $r=O(\log(n/\varepsilon))$.

4 Main Technical Lemma

The lemma can be seen as a generalization of a similar result proved for real-valued random variables in [GY14](who also have an additional restriction on the means of the random variables $Y_{j}$). However, the generalization to complex-valued variables is substantial and seems to require different proof techniques.

We then argue that $\exp(\sum_{j}W_{j})$ can be approximated by a polynomial $P(W_{1},\ldots,W_{n})$ of degree less than $k$ with small expected error. The polynomial $P$ is obtained by truncating the Taylor series expansion of the $\exp(\;)$ function. Once, we have such a low-degree polynomial approximator, the claim follows as limited independence fools low-degree polynomials.

To handle the general case where $Z_{j}$’s are not necessarily bounded, we use an inclusion-exclusion argument and exploit the fact that with high probability, not many of the $Z_{j}$’s (say more than $k/2$) will deviate too much from their expectation. We leave the details to the actual proof.

Preliminaries

For a complex valued random variable $Z$,

Unless otherwise stated $c,C$ denote universal constants.

Throughout we assume that $n$ is sufficiently large and that $\delta,\varepsilon>0$ are sufficiently small.

For positive functions $f,g,h$ we write $f=g+O(h)$ when $|f-g|=O(h)$.

For $n,m,\delta>0$ we say that a family of hash functions $\mathcal{H}=\{h:[n]\to[m]\}$ is $\delta$-biased if for any $r\leq n$ distinct indices $i_{1},i_{2},\ldots,i_{r}\in[n]$ and $j_{1},\ldots,j_{r}\in[m]$,

We say that such a family is $k$-wise independent if the above holds with $\delta=0$ for all $r\leq k$.

We say that a distribution over $\{\pm 1\}^{n}$ is $\delta$-biased or $k$-wise independent if the corresponding family of functions $h:[n]\to$ is.

Such families of functions can be generated efficiently using small seeds.

For $n,m,k,\delta>0$, there exist explicit $\delta$-biased families of hash functions $\mathcal{H}=\{h:[n]\to[m]\}$ that can be generated efficiently from a seed of length $s=O(\log(n/\delta))$. There are also, explicit $k$-wise independent families that can be generated efficiently from a seed of length $s=O(k\log(nm))$.

Taking the pointwise sum of such generators modulo $m$ gives a family of hash functions that is both $\delta$-biased and $k$-wise independent generated from a seed of length $s=O(\log(n/\delta)+k\log(nm))$.

We start with the simple observation that to $\delta$-fool an $(m,n)$-Fourier shape $f$, we can assume the functions in $f$ have bit-precision $2\log_{2}(n/\delta)$. This observation will be useful when we use PRGs for small-space machines to fool Fourier shapes in certain parameter regimes.

If a ${\mathsf{PRG}}$ $\mathcal{G}:\{0,1\}^{r}\to[m]^{n}$ $\delta$-fools $(m,n)$-Fourier shapes $f=\prod_{j}f_{j}$ when $\log(f_{j})$’s have bit precision $2\log_{2}(n/\delta)$, then $\mathcal{G}$ fools all $(m,n)$-Fourier shapes with error at most $2\delta$.

We collect some known results about pseudorandomness and prove some other technical results that will be used later.

We shall use ${\mathsf{PRG}}$s for small-space machines or read-once branching programs (ROBP) of Nisan [Nis92], [NZ96] and Impagliazzo, Nisan and Wigderson [INW94]. We extend the usual definitions of read-once branching programs to compute complex-valued functions; the results of [Nis92], [NZ96], [INW94] apply to this extended model readilyThis is because these results in fact give guarantees in terms of statistical distance..

An $(S,D,T)$-ROBP $M$ is a layered directed graph with $T+1$ layers and $2^{S}$ vertices per layer with the following properties.

A vertex $v$ in layer $i$, $0\leq i<T$ has $2^{D}$ edges to layer $i+1$ each labeled with an element of $\{0,1\}^{D}$.

There exists an explicit ${\mathsf{PRG}}$ $\mathcal{G}^{INW}:\{0,1\}^{r}\to\left(\{0,1\}^{D}\right)^{T}$ which $\varepsilon$-fools $(S,D,T)$-branching programs and has seed-length $r=O(D+S\log T+\log(T/\delta)\cdot(\log T))$.

For all $C>1$ and $0<c<1$, there exists an explicit ${\mathsf{PRG}}$ $\mathcal{G}^{NZ}:\{0,1\}^{r}\to\left(\{0,1\}^{D}\right)^{T}$ which $\varepsilon$-fools $(S,S,S^{C})$-branching programs for $\varepsilon=2^{-\log^{1-c}S}$ and has seed-length $r=O(S)$.

Fooling products of low-variance random variables

We now show one of our main technical claims that products of complex-valued random variables are fooled by limited independence if the sum of variances of the random variables is small. The lemma is essentially equivalent to saying that limited independence fools low-variance Fourier shapes.

We start with the following standard bound on moments of bounded random variables whose proof is deferred to appendix B.

We also use some elementary properties of the (complex-valued) log and exponential functions:

Claims (1), (2) follow from the Taylor series expansions for the complex-valued log and exponential functions.

We prove Lemma 4.1 or equivalently, Equation (3) by proving a sequence of increasingly stronger claims. We begin by proving that Equation (3) holds if $X_{j}$’s have small absolute deviation, i.e., lie in a disk of small radius about a fixed point.

Therefore, by Lemma 4.2, the expression in (4) is at most

Next, we relax the conditions to handle the case where we only require the means of the $X_{j}$’s be far from zero.

We assume throughout that $\sigma/\sqrt{k}$ is less than a sufficiently small constant; otherwise, there is nothing to prove. Further, note that there can be at most $k$ different indices $j\in[n]$ where $\sigma_{j}\geq\sigma/\sqrt{k}$. As even after conditioning on the values of the corresponding $Y$’s, the remaining $Y_{j}$’s are $(C-1)k$-independent, it suffices to prove the lemma when $\sigma_{j}\leq\sigma/\sqrt{k}$ for all $j$.

To apply Lemma 4.4, we consider a truncation of our random variables: define

We truncate the above expansion to only include terms corresponding to sets $S$ with $|S|<m$ for $m=O(k)$ to be chosen later. Let

Note that the expectation above is the same as what it would be if the $Y_{i}$’s were fully independent, in which case it is at most

Therefore, $Ck$-wise independence fools $P_{m}$ to error $2^{O(k)}\cdot(\sigma/\sqrt{k})^{k}$.

On the other hand, the expectation of $\binom{N}{m}$ is

Taking $m=3k/2$ yields a final error of $\exp(O(k))\cdot(\sigma/\sqrt{k})^{k}$. This completes our proof. ∎

Finally, we can extend our proof to cover the general case.

Note that it suffices to prove that Equation (3) holds. As before, it suffices to assume that $\sigma/\sqrt{k}\ll 1$ and that $\sigma_{i}\leq\sigma/\sqrt{k}$ for all $i$.

On the one hand if $m\leq 6k$, we note that for $C$ sufficiently large, the values of $Y_{1},\ldots,Y_{m}$ are independent of each other, and even after conditioning on them, the remaining $Y_{i}$’s are still $C^{\prime}k$-wise independent. Thus, applying Lemma 4.5 to the expectation of the product of the remaining $Y_{i}$ we find that the difference between the expectation of the product of $X$’s and product of $Y$’s is as desired.

Notice that so long as at least $3k$ of $Y_{1},\ldots,Y_{m}$ have absolute value less than $2(\sigma/\sqrt{k})^{1/3}$, then

Therefore, it suffices to show that this occurs except with probability at most $O(\sigma/\sqrt{k})^{k}$. Let $N$ be the number of $1\leq i\leq m$ so that $|Y_{i}|\geq 2(\sigma/\sqrt{k})^{1/3}.$ Note that

A Generator for high-variance Fourier shapes

In this section, we construct a generator that fools Fourier shapes with high variance.

We start with the simple but crucial observation that Fourier shapes with large variance have small expectation.

We build the generator in two steps. We first build a generator with seed-length $O(\log n)$ which achieves constant error for all $f$ with $\mathsf{Tvar}(f)\geq 1$. In the second step, we reduce the error down to $\delta$. This construction is inspired by a construction of Naor and Naor [NN93] of small-bias spaces.

Our goal in this subsection is get a generator with constant error for Fourier shapes where $\mathsf{Tvar}(f)=\Omega(1)$. We start by showing that when $\mathsf{Tvar}(f)=\Theta(1)$ (instead of just $\Omega(1)$), $O(1)$-wise independence is enough to fool $f$.

Let $f=\prod_{j}f_{j}$, $X\in_{u}[m]^{n}$. Now, by Lemma 4.1 applied to $Y_{j}=f_{j}(Z_{j})$, we have,

Note that by taking $p$ to be a sufficiently large constant compared to $c_{2}$, we can make the last bound arbitrary small.

for $p$ sufficiently large constant and some constant $0<c^{\prime}<1$. ∎

We reduce the general case of $\mathsf{Tvar}(f)\in[1,n]$ to the case above where $\mathsf{Tvar}(f)=\Theta(1)$ by using the Valiant-Vazirani technique of sub-sampling. For $B\subseteq[n]$ let $\mathsf{Tvar}(f_{B})=\sum_{i\in B}\sigma_{i}^{2}$. If we sample a random subset $B\subseteq[n]$ with $|B|\approx n/\mathsf{Tvar}(f)$ in a pairwise independent manner, we will get $\mathsf{Tvar}(f_{B})=\Theta(1)$ with $\Omega(1)$ probability. Since we do not know $\mathsf{Tvar}(f)$, we sample $\log(n)$ subsets whose cardinalities are geometrically increasing; one of them is likely to satisfy the desired bound.

We set up some notation that will be used in the remainder of this section.

The proof of this lemma is standard and is deferred to Appendix C.

This naturally suggests using an $O(1)$-wise independent distribution within each bucket. But using independent strings across the $\log(n)$ buckets would require a seed of length $O(\log(mn)\cdot(\log n))$. We analyze our generator assuming independence across distinct buckets, but then recycle the seeds using ${\mathsf{PRG}}$s for space bounded computation to keep the seed-length down to $O(\log(mn))$ (rather than $O(\log^{2}(n))$).

We now prove the main claim of this subsection.

Let $\pi\in_{u}\Pi$ and let $Z^{j}\sim[m]^{2^{j}}$ be an independent $p$-wise independent string for a parameter $p=O(1)$ to be chosen later. Define

In other words, the generator applies the string $Z^{j}$ to the coordinates in bucket $B_{j}$.

Observe that $f(Y)=\prod_{j=0}^{\log(n)-1}f^{j}(Z^{j})$. Since the $Z^{j}$’s are independent of each other

We next improve the seed-length of $\mathcal{G}_{1}^{\prime}$ using the ${\mathsf{PRG}}$ for ROBPs of Theorem 3.4. To this end, note that by Lemma 3.2 we can assume that every $\log(f_{i}(x_{i}))$, and hence every $\log(f^{j}(x^{j}))$, has bit precision at most $O(\log n)$ bits (since our goal is to get error $\delta=O(1)$). Further, each $Z^{j}$ can be generated efficiently with $O(\log(mn))$ random bits.

Thus, for a fixed permutation $\pi$, the computation of $f(\mathcal{G}^{\prime}(\pi,Z^{1},\ldots,Z^{T}))$ can be done by a $(S,D,T)$-ROBP where $S,T$ are $O(\log n)$ and $D=O(\log(mn))$: for $j\in\{1,\ldots,T\}$, the ROBP computes $f^{j}(Z^{j})$ and multiplies it to the product computed so far, which can be done using $O(\log n)$ bits of space. Let $\mathcal{G}^{NZ}:\{0,1\}^{r}\to\left(\{0,1\}^{D}\right)^{T}$ be the generator in Theorem 3.4 fooling $(S,D,T)$-ROBPs as above with error $\delta<(1-c^{\prime\prime})/2$. $\mathcal{G}^{NZ}$ has seedlength $O(\log(mn))$. Let

2 Reducing the error

Our generator will partition $[n]$ into $m=O((\log(1/\delta))^{5})$ buckets $B_{1},\ldots,B_{m}$, using a family of hash functions with the following spreading property:

We start by showing that the desired hash functions can be generated from a small-bias family of hash functions. We show that it satisfies the conditions of the lemma by standard moment bounds. The proof is in Appendix C

For all constants $C_{1}$, there exist constants $C_{2},C_{3}$ such that following holds. For all $\delta\geq 0$, there exists an explicit hash family $\mathcal{H}=\{h:[n]\to[T]\}$, where $T=C_{2}\log^{5}(1/\delta))$ which is $(C_{3}\log^{5}(1/\delta),C_{1}\log(1/\delta),\delta)$-spreading and $h\in_{u}\mathcal{H}$ can be sampled efficiently with $O(\log(n/\delta))$ bits.

where $c<1$ is the constant from Lemma 5.3. By the spreading property of $\mathcal{H}$, with probability at least $1-\delta$, $|I|\geq C\log(1/\delta)$. Therefore, for $C$ sufficiently large,

As in Lemma 5.5, we recycle the seeds for the various buckets using the PRGs for ROBPs. By Lemma 3.2, we may assume that $f^{j}$ has bit precision at most $O(\log(n/\delta))$ bits. Further note that

For a fixed hash function $h\in\mathcal{H}$, this can be computed by a $(S,D,T)$-ROBP where $S=O(\log(n/\delta))$ and $D=O(\log(mn))$, corresponding to the various possible seeds for $\mathcal{G}_{1}$. Let $\mathcal{G}^{INW}:\{0,1\}^{r}\to\left(\{0,1\}^{D}\right)^{T}$ be a generator fooling $(S,D,T)$-ROBPs as in Theorem 3.3 with error $\delta$ and define

The seed-length is dominated by the seed-length of $\mathcal{G}^{INW}$, which is

Alphabet reduction for Fourier shapes

In this section, we describe our alphabet-reduction procedure, which reduces the general problem of constructing an $\varepsilon$-PRG for $(m,n)$-Fourier shapes where $m$ could be much larger than $n$, to that of constructing an $\varepsilon/\log(m)$-PRG for $(n^{4},n)$-Fourier shapes. This reduction is composed of $O(\log\log m)$ steps where in each step we reduce fooling $(m,n)$-Fourier shapes to fooling $(\sqrt{m},n)$-Fourier shapes. Each of these steps in turn will cost $O(\log(m/\varepsilon))$ random bits, so that the overall cost is $O(\log(m/\varepsilon)\cdot(\log\log m))$. Concretely, we show the following:

Let $n,\delta>0$ and suppose that for some $r^{\prime}=r^{\prime}(n,\delta^{\prime})$, for all $m^{\prime}\leq n^{4}$ there exists an explicit generator $\mathcal{G}_{m^{\prime}}:\{0,1\}^{r_{1}}\to[m^{\prime}]^{n}$ which $\delta^{\prime}$-fools $(m^{\prime},n)$-Fourier shapes. For all $m$, there exists an explicit generator $\mathcal{G}_{m}:\{0,1\}^{r}\to[m]^{n}$ which $(\delta^{\prime}+\delta)$-fools $(m,n)$-Fourier shapes with seed-length $r=r^{\prime}+O(\log(m/\delta)\log\log(m))$.

We prove the claim by showing that for $m>n^{4}$, we can reduce $(\delta+\delta^{\prime})$-fooling $(m,n)$-Fourier shapes to that of $\delta^{\prime}$-fooling $(\sqrt{m},n)$-Fourier shapes with $O(\log(m/\delta))$ additional random bits. The theorem follows by applying the claim $\log\log(m)$ until the alphabet size drops below $n^{4}$ when we can use $\mathcal{G}_{m^{\prime}}$. This costs a total of $r^{\prime}+O(\log(m/\delta)\log\log(m))$ random bits, and gives error $\delta^{\prime}+\log\log(m)\delta$. The claim follows by replacing $\delta$ with $\delta/\log\log(m)$.

Thus, suppose that $m>n^{4}$ and for $D=\left\lfloor\sqrt{m}\right\rfloor$, we have a generator $\mathcal{G}_{D}:\{0,1\}^{r_{D}}\to[D]^{n}$ which $\delta^{\prime}$-fools $(D,n)$-Fourier shapes. The generator $\mathcal{G}_{m}$ works as follows:

Generate a matrix $X\in[m]^{D\times n}$ where

Each column of $X$ is from a pairwise independent distribution over $[m]^{D}$.

The different columns are $k$-wise independent for $k=C\log(1/\delta)/\log(m)$ for some sufficiently large constant $C$.

Generate $Y=(Y_{1},\ldots,Y_{n})=\mathcal{G}_{D}(z)\in[D]^{n}$ for $z\in_{u}\{0,1\}^{r_{D}}$.

$\mathcal{G}_{m}$ outputs $Z=(Z_{1},\ldots,Z_{n})\in[m]^{n}$ where $Z_{j}=X[Y_{j},j]$ for $j\in[n]$.

Each column of $X$ can be generated using a seed of length $2\log m$. By using seeds for various columns that are $k$-wise independent, generating $X$ requires seedlength $O(k\log m)=O(\log(1/\delta))$ (as $m>n^{2}$), while the number of bits needed to generate $Z$ is $r_{D}+O(\log(1/\delta))$.

Let $X^{\prime},Y^{\prime}$ be random variables distributed uniformly over $[m]^{D\times n}$ and $[D]^{n}$ respectively. Let $Z^{\prime}_{j}=X^{\prime}[Y^{\prime}_{j},j]$ for $j\in[n]$, so that $Z^{\prime}$ is uniform over $[m]^{n}$ and $f(Z^{\prime})=f^{X^{\prime}}(Y^{\prime})$. Our goal is to show that $f(Z^{\prime})$ and $f(Z)$ are close in expectation. We do this by replacing $X^{\prime}$ and $Y^{\prime}$ by $X$ and $Y$ respectively.

That we can replace $Y^{\prime}$ with $Y$ follows from the pseudorandomness of $\mathcal{G}_{D}$. For any fixed $x\in[m]^{n}$, as $\mathcal{G}_{D}$ fools $(D,n)$-Fourier shapes,

We now show that for truly random $Y^{\prime}$, one can replace $X$ by $X^{\prime}$. Note that

The random variables $A_{1},\ldots,A_{n}$ are $k$-wise independent. Further, we have

where the second to last inequality follows becase $n\leq m^{1/4}$ and $D\geq\sqrt{m}/2$, and the last holds for $k=C\log(1/\delta)/\log(m)$ for a sufficiently big constant $C$. Equation 9 now follows from Equations (11) and (10).

Dimension reduction for low-variance Fourier shapes

We next describe our dimension reduction step for low-variance Fourier shapes. We start with an $(m,n)$-Fourier shape where $m\leq n^{4}$ and $\mathsf{Tvar}(f)\leq\log(n/\delta)^{c}$. We show how one can reduce the dimension to $t=\sqrt{n}$, at a price of a blowup in the alphabet size $m^{\prime}$ which now becomes $(n/\delta)^{c}$ for some (large) constant $c$.

Let $\delta>0$, $n>0$ and $t=\lceil\sqrt{n}\rceil$. There is a constant $c$ and $m^{\prime}\leq(n/\delta)^{c}$ such that the following holds: if there exists an explicit ${\mathsf{PRG}}$ $\mathcal{G}^{\prime}:\{0,1\}^{r^{\prime}}\to[m^{\prime}]^{t}$ with seed-length $r^{\prime}=r^{\prime}(n,\delta^{\prime})$ which $\delta^{\prime}$-fools $(m^{\prime},t)$-Fourier shapes, then there exists an explicit generator $\mathcal{G}:\{0,1\}^{r}\to[m]^{n}$ with seed-length $r=r^{\prime}+O(\log(n/\delta))$ which $(\delta+\delta^{\prime})$-fools $(m,n)$-Fourier shapes $f$ with $m\leq n^{4}$ and $\mathsf{Tvar}(f)\leq n^{1/9}$.

We start by constructing an easy to analyze generator $G_{1}$ which hashes co-ordinates into buckets using $k$-wise independence and then uses independent $k$-wise independent strings within a bucket. Let

where $C$ will is a sufficiently large constant. Let $\mathcal{H}:\{[n]\to t\}$ be a $k$-wise independent family of hash functions. Let $G_{0}:\{0,1\}^{r_{0}}\to[m]^{n}$ be a $k$-wise independent generator over $[m]^{n}$. Define a new generator $G_{1}:\mathcal{H}\times(\{0,1\}^{r_{0}})^{t}\to[m]^{n}$ as:

We argue that $G_{1}$ fools $(m,n)$-Fourier shapes with small total variance as in the theorem. Our analysis proceeds as follows:

With high probability over $h\in_{u}\mathcal{H}$, each of the $f^{j}$’s has low variance except for a few heavy co-ordinates (roughly $\mathsf{Tvar}(f)/t$ after dropping $k/2$ heavy coordinates).

Within each bin we have $k$-wise independence, whereas the distributions across bins are independent. So even conditioned on the heavy co-ordinates in a bin, the remaining distribution in the bin is $k/2$-wise independent. Hence each $f^{j}$ is fooled by Lemma 4.1.

For $\alpha>0$, to be chosen later, let $L=\{j\in[n]:\sigma^{2}(f_{j})\geq\alpha\}$ denote the $\alpha$-large indices and $S=[n]\setminus L$ denote the small indices. We call a hash function $h\in\mathcal{H}$ $(\alpha,\beta)$-good if the following two conditions hold for every bin $h^{-1}(j)$ where $j\in[t]$:

The bin does not have too many large indices: $|h^{-1}(j)\cap L|\leq k/2$.

The small indices in the bin have small total variance:

Using standard moment bounds for $k$-wise independent hash functions one can show that $h\in_{u}\mathcal{H}$ is $(\alpha,\beta)$-good with probability at least $1-n^{-\Omega(k)}$ for $\alpha=n^{-\Omega(1)}$ and $\beta=n^{-\Omega(1)}$. We defer the proof of the following Lemma to Appendix D.

Let $\mathsf{Tvar}(f)\leq n^{1/9}$ and let $\mathcal{H}=\{h:[n]\to[t]\}$ be a $k$-wise independent family of hash functions for $t=\Theta(\sqrt{n})$. Then $h\in\mathcal{H}$ is $(n^{-1/3},n^{-1/36})$-good with probability $1-O(k)^{k/2}n^{-\Omega(k)}$.

We next argue that if $h\in\mathcal{H}$ is $(\alpha,\beta)$-good then, $k$-wise independence is sufficient to fool $f^{j}$ for each $j\in[t]$.

Let $h\in\mathcal{H}$ be $(\alpha,\beta)$-good, and let $j\in[t]$. For $Z^{\prime}\sim[m]^{n}$ $k$-wise independent, and $Z^{\prime\prime}\in_{u}[m]^{n}$,

Fix $j\in[t]$. By relabelling coordinates, let us assume that $h^{-1}(j)=\{1,\ldots,n_{j}\}$ and $L\cap h^{-1}(j)=\{1,\ldots,r\}$, where $r\leq k/2$. As $Z^{\prime}$ is $k$-wise independent, $(Z^{\prime}_{1},\ldots,Z^{\prime}_{r})$ is uniformly distributed over $[m]^{r}$. We couple $Z^{\prime}$ and $Z^{\prime\prime}$ by taking $Z^{\prime}_{i}=Z^{\prime\prime}_{i}$ for $i\leq r$. Even after conditioning on these values, $Z^{\prime}_{r+1},\ldots,Z^{\prime}_{n_{j}}$ are $k/2$-wise independent.

We use these lemmas to prove Theorem 7.1.

Recall that $G_{1}(h,z_{1},\ldots,z_{t})=Z$ where $Z^{j}=G_{0}(z_{j})$ for $j\in[t]$. Since the $z_{j}$s are independent, so are the $Z^{j}$’s. Hence,

By Lemma 7.3, for $(n^{-1/3},n^{-1/36})$-good $h$, if $Y\in_{u}[m]^{n}$, then

Combining the above equations we get that for $Y\in_{u}[m]^{n}$,

where the last inequality holds by taking $C$ in Equation (12) to be a sufficiently large constant.

We next derandomize the choice of the $z^{j}$’s by using a PRG for appropriate Fourier shapes. Let $r_{0}$ be the seed-length of the generator $G_{0}$ obtained by setting $k=C\log(n/\delta)/(\log n)$ as above, and let $c$ be such that $r_{0}\leq c\log(n/\delta)$. Let

respectively. Observe that $\bar{f}$ is a Fourier shape, and

By assumption, we have an explicit generator $\mathcal{G}^{\prime}:\{0,1\}^{r^{\prime}}\to[m^{\prime}]^{t}$ which $\delta^{\prime}$-fools $(m^{\prime},t)$-Fourier shapes. We claim that $\mathcal{G}:\mathcal{H}\times\{0,1\}^{r^{\prime}}\to[m]^{n}$ defined as