Inequalities and tail bounds for elementary symmetric polynomial with applications

Introduction

The main message of this paper is that small total variance is sufficient to ensure that the product rule holds approximately even under $k$-wise independence.

Let $X_{1},\ldots,X_{n}$ be random variables each distributed in the range $$, with mean$\mu_{i}$and variance$\sigma^{2}_{i}$repectively. Let$\sigma^{2}=\sum_{i}\sigma_{i}^{2}$. There exist constants$c_{1}>1$and$1>c_{2}>0$such that under any$k$-wise independent distribution${\mathcal{D}}$,

Specifically, if $\sigma<1/(2c_{1})$ then $k=O(\log(1/\delta)/\log(1/\sigma))$-wise independence suffices for Equation (1).

An important restriction that naturally arises is positivity, where each $X_{i}$ lies in the interval $$. This setting of parameters (positive variables, small total variance) is important for the applications considered in this paper: pseudorandom generators for combinatorial rectangles [EGL+98, LLSZ97] and min-wise independent permutations [BCFM00]. The former is an important problem in the theory of unconditional pseudorandomness which has been studied intensively [EGL+98, LLSZ97, SSZZ99, ASWZ96, Lu02, GMR+12]. Min-wise independent hashing was introduced by Broder et al. [BCFM00] motivated by similarity estimation, and further studied by [Ind99, BCM98, SSZZ99]. [SSZZ99] showed that PRGs for rectangles give min-wise independent hash functions.

The results of [EGL+98, Ind99] tell us that under $k$-wise independence, positivity and boundedness, the LHS of Equation (1) is bounded by $\exp(-\Omega(k))$, hence $k=O(\log(1/\delta))$ suffices for error $\delta$. In contrast, we have seen that such a bound cannot hold in the $$case. However, once the variance is smaller than some constant, our bound beats this bound even in the$$ setting. Concretely, when $\sigma^{2}<n^{-\varepsilon}$ for some $\varepsilon>0$, our result says that $O(1)$-wise independence suffices for inverse polynomial error in Equation (1), as opposed to $O(\log(n))$-wise independence. This improvement is crucial in analyzing PRGs and hash functions in the polynomially small error regime. A recent result of [GMR+12] achieves near-logarithmic seed-length for both these problems, even in the regime of inverse polynomial error. Their construction is simple, but its analysis is not. Using our results, we give a modular analysis of the pseudorandom generator construction for rectangles of [GMR+12], using the viewpoint of hash functions.

Our analysis is simpler and perhaps more intuitive. It also improves the seed-length of the construction, getting the dependence on the dimension $n$ down to $O(\log\log(n))$ as opposed to $O(\log(n))$, which (nearly) matches a lower bound due to [LLSZ97]. Given the basic nature of the question, we feel our results might find other applications. Very recently, [GKM15] constructed the first pseudorandom generators with near-logrithmic seed-length for several classes of functions including halfspaces, modular tests and combinatorial shapes. The key technical ingredient of their work is a generalization of Theorem 1 to the setting where each $X_{i}$ takes values in the unit complex disc.

The main technical ingredient in our work is a new analytic inequality about symmetric polynomials in real variables which we believe is independently interesting. The $k$’th symmetric polynomial in $a=(a_{1},a_{2},\ldots,a_{n})$ is defined as

We give an overview of the new inequality, its use in the derivation of bounds under limited independence, and finally the application of these bounds to the construction of pseudorandom generators and hash functions.

The elementary polynomials appear as coefficients of a univariate polynomial with real roots, since $\prod_{i\in[n]}(\xi+a_{i})=\sum_{k=0}^{n}\xi^{k}S_{n-k}(a)$. Symmetric polynomials have been well studied in mathematics, dating back to classical results of Newton and Maclaurin (see [Ste04] for a survey). This work focuses on their growth rates. Specifically, we study how local information on $S_{k}(a)$ for two consecutive values of $k$ implies global information for all larger values of $k$.

It is easy to see that symmetric polynomials over the real numbers have the following property:

Over the real numbers, if $S_{1}(b)=S_{2}(b)=0$ then $b=0$.

This is equivalent to saying that if $p(\xi)$ is a real univariate polynomial of degree $n$ with $n$ nonzero roots and $p^{\prime}(0)=p^{\prime\prime}(0)=0$ then $p\equiv 0$. This does not hold over all fields, for example, the polynomial $p(\xi)=\xi^{3}+1$ has three nonzero complex roots and $p^{\prime}(0)=p^{\prime\prime}(0)=0$.

That is, if $S_{1}(a),S_{2}(a)$ are small in absolute value, then so is everything that follows. We provide an essentially optimal bound.

The parameters promised by Theorem 2 are tight up to an exponential in $k$ which is often too small to matter (we do not attempt to optimise the constants). For example, if $a_{i}=(-1)^{i}$ for all $i\in[n]$ then $|S_{1}(a)|\leq 1$ and $|S_{2}(a)|\leq n+1$ but $S_{k}(a)$ is roughly $(n/k)^{k/2}$.

A more general statement than Fact A actually holds (see Appendix A for a proof).

We prove a robust version of this fact as well: A twice-in-a-row bound on the increase of the symmetric functions implies a bound on what follows.

Theorem 3 is proved by reduction to Theorem 2. The proof of Theorem 2 is analytic and uses the method of Lagrange multipliers, and is different from that of [GMR+12] which relied on the Newton-Girrard identities. The argument is quite general, and similar bounds may be obtained for functions that are recursively defined. The proof can be found in Section 2.

Stronger bounds are known when the inputs are nonnegative. When $a_{i}\geq 0$ for all $i\in[n]$, the classical Maclaurin inequalities [Ste04] imply that $S_{k}(a)\leq(e/k)^{k}(S_{1}(a))^{k}$. In contrast, when we do not assume non-negativity, one cannot hope for such bounds to hold under the assumption that $|S_{1}(a)|$ or any single $|S_{k}(a)|$ is small (cf. the alternating signs example above).

2 Expectations of products under limited independence

We return to the question alluded to earlier about how much independence is required for the approximate product rule of expectation. This question arises in the context of min-wise hashing [Ind99], PRGs for combinatorial rectangles [EGL+98, GMR+12], read-once DNFs [GMR+12] and more.

We briefly outline our approach. We start from the results of [EGL+98, Ind99] who give an error bound of $\exp(-k)$. To prove this, they consider random variables $Y_{i}=1-X_{i}$, so that

Our approach replaces inclusion-exclusion by a Taylor-series style expansion about the mean, as in [GMR+12]. Let us assume $\mu_{i}\neq 0$ and let $X_{i}=\mu_{i}(1+Z_{i})$. Thus,

Let $\cal{D}$ denote a distribution over $Z=(Z_{1},\ldots,Z_{n})$ as above where the $Z_{i}$s are $(2k+2)$-wise independent. For $t>0$ andA weaker but more technical assumption on $t,\sigma,k$ suffices, see Equation (24). $16et\sigma\leq 1$,

3 Applications to pseudorandom generators and hash functions

A hash function is a map $h:[n]\rightarrow[m]$. Let $\mathcal{U}$ denote the family of all hash functions $h:[n]\rightarrow[m]$. Let $\mathcal{H}\subseteq\mathcal{U}$ be a family of hash functions. For $S\subseteq[n]$, let $\min h(S)=\min_{x\in S}h(x)$. The notion of min-wise independent hashing was introduced by Broder et al. [BCFM00] motivated by similarity estimation, and independently by Mulmuley [Mul96] motivated by computational geometry. The following generalization was introduced by Broder et al. [BCM98]:

Combinatorial rectangles are a well-studied class of tests in pseudorandomness [EGL+98, LLSZ97, SSZZ99, ASWZ96, Lu02, GMR+12]. In addition to being a natural class of statistical tests, constructing generators for them with optimal seeds (up to constant factors) will improve on Nisan’s generator for logspace [ASWZ96], a long-standing open problem in derandomization.

A combinatorial rectangle is a function $f:[m]^{n}\rightarrow\{0,1\}$ which is specified by $n$ co-ordinate functions $f_{i}:[m]\rightarrow\{0,1\}$ as $f(x_{1},\ldots,x_{n})=\prod_{i\in m}f_{i}(x_{i})$. A map $\mathcal{G}:\{0,1\}^{r}\rightarrow[m]^{n}$ is a ${\mathsf{PRG}}$ for combinatorial rectangles with error $\varepsilon$ if for every combinatorial rectangle $f:[m]^{n}\rightarrow\{0,1\}$,

We take the view of $\mathcal{G_{MR}}$ as a collection of hash functions $g:[n]\to[m]$, based on iterative applications of an alphabet squaring step. We describe the generator formally in Section 5. We start by observing that fooling rectangles is easy when $m$ is small; $O(\log(1/\delta))$-wise independnce suffices, and this requires $O(\log(1/\delta)\log(m))=O(\log(1/\delta))$ random bits for $m=O(1)$.

The key insight in [GMR+12] is that gradually increasing the alphabet is also easy (in that it requires only logarithmic randomness). Assume that we have a hash function $g_{0}:[n]\to[m]$ and from it, we define $g_{1}:[n]\to[m^{2}]$. To do this, we pick a function $g_{1}^{\prime}:[n]\times[m]\to[m^{2}]$ and set $g_{1}(i)=g_{1}^{\prime}(i,g_{0}(i))$. The key observation is that it suffices to pick $g_{1}^{\prime}$ using only $O(\log(1/\delta)/\log(m))$-wise independence (rather than the $O(\log(1/\delta))$-wise independence needed for one shot).

Let $\mathcal{G_{MR}}$ be the family of hash functions from $[n]$ to $[m]$ defined in Section 5.1 with error parameter $\delta>0$. The seed length is at most $O((\log\log(n)+\log(m/\delta))\log\log(m/\delta))$. Then, for every $S_{1},\ldots,S_{n}\subseteq[m]$,

This improves the [GMR+12] bound in the dependence on $n$ and $\delta$ (their bound was $O(\log(mn/\delta)\log\log(m)+\log(1/\delta)\log\log(1/\delta)\log\log\log(1/\delta))$). In particular, the dependence on $n$ reduces from $\log(n)$ to $\log\log(n)$The reason $\log\log(n)$ seedlength is possible is because every rectangle can be $\varepsilon$-approximated by one that depends only on $O(m\log(1/\varepsilon))$ co-ordinates. Hence the number of functions to fool grows polynomially in $n$, rather than exponentially.. [LLSZ97] showed a lower bound of $\Omega(\log(m)+\log(1/\varepsilon)+\log\log(n))$ even for hitting sets, so our bound is tight upto the $\log\log(m/\delta)$ factor. While [LLSZ97] constructed hitting-set generators for rectangles with near-optimal seedlength, we are unaware of previous constructions of pseudorandom generators for rectangles where the dependence of the seedlength on $n$ is $o(\log(n))$.

Combining this with Theorem 19, we get the following corollary.

4 Subsequent work

Very recently, Gopalan, Kane and Meka [GKM15] constructed the first pseudorandom generators with seed-length $O((\log(n/\delta)\log\log(n/\delta)^{2})$ for several classes of functions including halfspaces, modular tests and combinatorial shapes. The key technical ingredient of their work is a generalization of Theorem 1 to the setting where the $X_{i}$s are complex valued random variables lying in the unit disc. Their proof however is very different from ours, and in particular it does not imply the inequalities and tail bounds for symmetric polynomials that are proved here.

We present the proofs of our inequalities for symmetric polynomials in Section 2 and tail bounds for symmetric polynomials in Section 3. We use these bounds to prove Theorem 1 on products of low-variance variables in Section 4 and to analyze the [GMR+12] generator in Section 5.

Inequalities for symmetric polynomials

under the constraint that $S_{1}(a)$ is fixed. Since $\phi_{k}$ is projectively defined, its supremum is attained in the (compact) unit sphere, and is therefore a maximum. Choose $a\neq 0$ to be a point that achieves the maximum of $\phi_{k}$. We assume, without loss of generality, that $S_{1}(a)$ is non-negative (if $S_{1}(a)<0$, consider $-a$ instead of $a$). There are two cases to consider:

The first case is that for all $i\in[n]$,

In this case we do not need the induction hypothesis and can in fact replace each $a_{i}$ by its absolute value. Let $P\subseteq[n]$ be the set of $i\in[n]$ so that $a_{i}\geq 0$. Then by Equation (9),

The second case is that there exists $i_{0}\in[n]$ so that

Hence, for all $\delta$ close enough to zero so that $\sum_{i}\delta_{i}=0$,

For the above inequality to hold for all such $\delta$, it must be that there is $\lambda$ so that for all $i\in[n]$,

To see why this is true, set $\lambda_{i}=a_{i}S_{k}(a)k-(S^{2}_{1}(a)+E_{2}(a))S_{k-1}(-i)$ . We now have $\lambda_{1},\ldots,\lambda_{n}$ so that

for every $\delta_{1},\ldots,\delta_{n}$ of sufficiently small norm where $\sum_{i}\delta_{i}=0$. We claim that this implies that in fact $\lambda_{i}=\lambda$ for every $i$. To see this, assume for contradiction that $\lambda_{1}\neq\lambda_{2}$ and $|\lambda_{1}|>|\lambda_{2}|$. Set

for $\mu>0$ sufficiently small. It follows that $\sum_{i}\delta_{i}=0$ and $\sum_{i}\lambda_{i}\delta_{i}=\mu(\lambda_{1}\lambda_{2}-\lambda_{1}^{2})<0$ so Equation (12) is violated.

This specifically holds for $i_{0}$, so using (10) we have

To apply induction we need to bound $S_{1}^{2}(-i_{0})+E_{2}(-i_{0})$ from above. Since

The proof is by reduction to Theorem 2. Assume $a_{1},\ldots,a_{m}$ are nonzero and $a_{m+1},\ldots,a_{n}$ are zero. Denote $a^{\prime}=(a_{1},\ldots,a_{m})$ and notice that for allFor $k>m$ we have $S_{k}(a)=0$ so there is nothing to prove. $k\in[n]$,

Tail bounds under limited independence

The goal is proving a tail bound on the behaviour of the symmetric functions under limited independence.

We start by obtaining tail estimates, under full independence. Let $\cal{U}$ denote the distribution over $X=(X_{1},\ldots,X_{n})$ where $X_{1},\ldots,X_{n}$ are independent.

Since the expectation of $X_{i}$ is zero for all $i\in[n]$,

If $2e^{1/2}t\sigma\leq k^{1/2}$ then by the union bound

In the following the underlying probability distribution over $X$ is $\cal{D}$. By Lemma 9, for $i\in\{k,k+1\}$,

which occurs with probability at least $1-2t^{-2k}$. Fix $x=(x_{1},\ldots,x_{n})$ such that Equation (17) holds.

We claim that there must exist $k_{0}\in\{0,\ldots,k-1\}$ for which the following bounds hold:

To see this, mark point $j\in\{0,\ldots,k+1\}$ as high if

A point is marked both high and low if equality holds. Observe that is marked high (and low) since $S_{0}(x)=1$ and $k$ and $k+1$ are marked low by Equation (17). This implies the existence of a triple $k_{0},k_{0}+1,k_{0}+2$ where the first point is high and the next two are low.

Let $\gamma>0$ be the smallest number so that the following inequalities hold:

By definition, one of Equations (21) and (22) holds with equality so

Observe further that $\gamma\leq t\sigma$ by Equations (18), (19) and (20). Combining this with the bounds in Equations (19) and (20)

Equations (21) and (22) let us apply Theorem 3 with $C=\gamma\sqrt{k_{0}+1}$ and $h\geq 3$ to get

Bounding $|S_{k_{0}}|$ by Equation (23), we get

As in Lemma 11, fix $x=(x_{1},\ldots,x_{n})$ such that Equation (17) holds (the random vector $X$ has this property with $\cal{D}$-probability at least $1-2t^{-2k}$). By the proof of lemma, since by assumption $6et\sigma<1/2$,

For this section, let $X_{1},\ldots,X_{n}$ be so that each $X_{i}$ is uniform over $\{-1,1\}$. Thus $\sigma^{2}=\sum_{i}\mathsf{Var}[X_{i}]=n$. By Lemma 9, we have

implies that for any $(2k+2)$-wise independent distribution,

Limited independence fools products of bounded variables

In this section we work with the following setup. We have $n$ random variables $X_{1},\ldots,X_{n}$ each distributed in the interval $$. Let$\mu_{i}$and$\sigma_{i}^{2}$denote the mean and variance of$X_{i}$, and let$\sigma^{2}=\sum_{i=1}^{n}\sigma_{i}^{2}$. We will typically use$\mathcal{U}$to denote the distribution where the$X_{i}$s are fully independent, and${\mathcal{D}}$ to denote distributions with limited independence.

There exist constants $c,c^{\prime}>0$ such that under any $ck$-wise independent distribution ${\mathcal{D}}$,

Define $H\subset[n]$ to be the set of indices such that $|\mu_{i}|\leq\sqrt{\sigma}$. Note that if $H\geq 2k$, then we are done since if $c\geq 2$, then

Further, since the variables are bounded in $$, we have

The same bound also holds under $\mathcal{U}$, hence

So now assume that $|H|\leq 2k$. Let $T=H\setminus[n]$. Even after conditioning on the outcome of variables in $H$, the resulting distribution on $T$ is $(c-2)k=c^{\prime\prime}k$-wise independent. Since the product of variables in $H$ has absolute value at most $1$, it suffices to show that for a $c^{\prime\prime}k$-wise independent distribution ${\mathcal{D}}$,

For ease of notation, we shall assume that $T=[m]$ for some $m\leq n$. We may assume that $m>c^{\prime\prime}k$ else there is nothing to prove.

Let us write $X_{i}=\mu_{i}(1+Z_{i})$, so that $Z_{i}$ has mean and variance $\sigma_{i}^{2}/\mu_{i}^{2}$. We write

For a $c^{\prime\prime}k$-wise independent distribution ${\mathcal{D}}$,

We first show how to finish the proof of Theorem 13 with this claim. We have

The first two are bounded by $(c^{\prime}\sigma^{k})/2$ by the claim, and the last is since $c^{\prime\prime}k$-wise independence fools degree $4k$ polynomials for $c^{\prime\prime}>4$.

Recall that the $X_{i}$s for $i\in[m]$ have expectation $\mu_{i}$ where $|\mu_{i}|\geq\sqrt{\sigma}$. We let $X_{i}=\mu_{i}(1+Z_{i})$, where $Z_{i}$ has mean and variance $\bar{\sigma}_{i}^{2}$ where

Hence the total variance of the $Z_{i}$s can be bounded by

Let $G$ denote the event that $|P(Z)-P^{\prime}(Z)|\leq 2(6e\sqrt{\bar{\sigma}})^{4k}$. Letting $t=1/\sqrt{\bar{\sigma}}$ and applying Theorem 4, for $c^{\prime\prime}>8k+2$

Analyzing the [GMR+12] generator

Gopalan et al. [GMR+12] proposed and analyzed a ${\mathsf{PRG}}$ for combinatorial rectangles, which we denote by $\mathcal{G_{MR}}$. In this section, we provide a different analysis of their construction, which is based on our results concerning the symmetric polynomials. Our analysis is simpler and follows the intuition that products of low variance events are easy to fool using limited independence. It also improves one their seedlength in the dependence on $n,\delta$ (see the discussion following Theorem 7).

Let $\mathcal{U}$ denote the uniform distribution on $[m]^{n}$, and let ${\mathcal{D}}$ be a distribution on $[m]^{n}$. For $x\in[m]^{n}$ and $K\subseteq[n]$, let $x_{K}=(x_{i}:i\in K)$. We sometimes abuse notation and write $x_{K}$ instead of the probability distribution of $x_{K}$. We denote by $d_{TV}$ the total variation distance.

A distribution ${\mathcal{D}}$ on $[m]^{n}$ is $(k,\varepsilon)$-wise independent if for every $K\subseteq[n]$ of size $k$, and $x\in{\mathcal{D}},y\in\mathcal{U}$, we have $d_{TV}(x_{K},y_{K})\leq\varepsilon$.

Such distributions can be generated using seed length $O(\log\log(n)+k\log(m)+\log(1/\varepsilon))$ when $m$ is a power of $2$ using standard constructions [NN93]. We can also assume that every co-ordinate is uniformly random in $[m]$. See the appendix for details.

(by adding the string $(a,a,\ldots,a)$ modulo $m$, where $a\in[m]$ is uniformly random).

Being $(k,\varepsilon)$-wise independent is equivalent to saying that for every $K\subseteq[n]$ of size $k$ and every $f:[m]^{k}\rightarrow\{0,1\}$,

The following more general property holds. Let $P$ be a real linear combination of combinatorial rectangles,

We use an alternate view of $\mathcal{G_{MR}}$ as a collection of hash functions $g:[n]\rightarrow[m]$. The generator $\mathcal{G_{MR}}$ is based on iterative applications of an alphabet increasing step. The first alphabet $m_{0}$ is chosen to be large enough, and at each step $t>1$ the size of the alphabet $m_{t}$ is squared $m_{t}=m_{t-1}^{2}$. There is a constant $C>0$ so that the following holds. Denote by $\delta$ the error parameter of the generator. Let $T\leq C\log\log(m)$ be the first integer so that $m_{T}\geq m$. Let $\delta^{\prime}=\delta/T$.

Base Case: Let $m_{0}\geq C\log(1/\delta)$ be a power of $2$. Sample $g_{0}:[n]\rightarrow[m_{0}]$ using a $(k_{0},\varepsilon_{0})$-wise independent distribution on $[m_{0}]^{n}$ with

This requires seed length $O(\log\log(n)+\log(\log\log(m)/\delta)\log\log(\log\log(m)/\delta))$.

Squaring the alphabet: Pick $g^{\prime}_{t}:[m_{t-1}]\times[n]\rightarrow[m_{t}]$ using a $(k_{t},\varepsilon_{t})$-wise independent distribution over $[m_{t}]^{m_{t-1}\times n}$ with

Define a hash function $g_{t}:[n]\rightarrow[m_{t}]$ as

This requires seed length $O(\log\log(n)+\log(m_{t})+\log(\log\log(m)/\delta))$.

2 Analyzing the generator

We first analyze the base case using the inclusion-exclusion approach of [EGL+98]. We need to extend their analysis to the setting where the co-ordinates are only approximately $k$-wise independent.

Let ${\mathcal{D}}$ be a $(k,\varepsilon)$-wise independent distribution on $[m]^{n}$ with $k$ odd. Then,

Let $p_{i}=|S_{i}|/m$, and $q_{i}=1-p_{i}$. Observe that

We consider two cases based on $\sum_{i}q_{i}$.

Case 1: When $\sum_{i}q_{i}\leq k/(2e)$. Since every non-zero $q_{i}$ is at least $1/m$, there can be at most $mk/(2e)$ indices $i$ so that $q_{i}>0$. For $i$ so that $q_{i}=0$, we have $S_{i}=[m]$, so we can drop such indices and assume $n\leq mk/(2e)$. By Bonferroni inequality, since $k$ is odd,

A similar bound holds for $h$. The $(k,\varepsilon)$-wise independence thus implies

The second term is twice $S_{k}(q_{1},\ldots,q_{n})$, which we can bound by Maclaurin’s identity as

Case 2: When $\sum_{i}q_{i}>k/2e$. Once again, we drop indices $i$ so that $q_{i}=0$. Consider the largest $n^{\prime}$ such that

Repeating the argument from Case 1 for this $n^{\prime}$,

To analyze the iterative steps, we use the following lemma:

There is $C>0$ so that the following holds for $\delta>0$ small enough. Assume

If $|H|\geq k$, we show that the probabilities are small which means that they are close. Indeed, let $H^{\prime}$ be the first $k$ indices in $H$. First,

Fooling the Tail:

We may assume that $q_{i}\geq 1/m$ and $p_{i}>0$ for all $i\in T$, since otherwise $S_{i}$ is trivial and we can drop such an index. As in the proof of Lemma 16, by restricting to a subset if necessary, we can also assume that

For simplicity of notation, we denote $|T|$ by $n$. Therefore, $n\leq Cm\log(1/\delta)$.

Since $g^{\prime}(a,i)$ is uniform over $S_{i}$,

We will show that $P_{k}(A)$ is a good approximation to $P_{n}(A)$ under $(O(k),\varepsilon^{O(1)})$-wise independence, hence under both ${\mathcal{D}}$ and $\mathcal{U}$.

Plugging in the bounds from Equations (34):

We argue for ${\mathcal{D}}$, the same argument holds for $\mathcal{U}$. Write

If $A_{1},\ldots,A_{n}$ are $(O(k),0)$-wise independent, then, by Lemma 9,

Hence, under $(O(k),\varepsilon)$-wise independence,

Denote by $\neg G$ the complement of $G$. Write

It remains to bound the second term. Bound

We are ready to prove the main theorem of this section.

The proof uses an hybrid argument. The $\mathcal{G_{MR}}$ generator chooses $g_{0}:[n]\rightarrow[m_{0}]$, and then $g^{\prime}_{1},\ldots,g^{\prime}_{T}$ where $g^{\prime}_{t}=[m_{t-1}]\times[n]\rightarrow[m_{t}]$ has error $\delta^{\prime}=\delta/T$ and defines

Let $h_{0},h^{\prime}_{1},\ldots,h^{\prime}_{t}$ be truly random hash functions with similar domains and ranges. For $0\leq t,l\leq T$, define the hybrid family $\mathcal{G}^{l}_{t}=\{f^{l}_{t}:[m]\rightarrow[n]\}$ as follows: for $t=0$ and every $l$,

For every $l$, let $\mathcal{G}^{l}=\mathcal{G}^{l}_{T}$. Thus, $\mathcal{G}^{0}=\mathcal{G_{MR}}$ and $\mathcal{G}^{T}=\mathcal{U}$. We will show by induction on $l\geq 1$ that

The desired bound then follows by the triangle inequality.

In the base case when $l=1$, couple $\mathcal{G}^{0}$ and $\mathcal{G}^{1}$ by picking the same $g^{\prime}_{1},\ldots,g^{\prime}_{T}$, and use them to define the function $f^{\prime}:[m_{1}]\times[n]\rightarrow[m]$ so that

by applying Lemma 16 with $k=O(\log(1/\delta^{\prime}))$ and $\varepsilon=\delta^{\prime}\cdot m_{0}^{-O(k)}$.

For the inductive case $l>1$, couple $\mathcal{G}^{l}$ and $\mathcal{G}^{l-1}$ by picking the same $g^{\prime}_{l+1},\ldots,g^{\prime}_{T}$, and pick $x\in[m_{l-1}]^{n}$ uniformly at random. There is a function $f^{\prime}:[m_{l}]\times[n]\rightarrow[m]$ so that

Acknowledgements

We thank Nati Linial, Raghu Meka, Yuval Peres, Dan Spielman, Avi Wigderson and David Zuckerman for helpful discussions. We thank an anonymous referee for pointing out an error in the statement of Theorem 4 in a previous version of the paper.

References

Appendix A Missing Proofs

Consider $p^{(n-k-1)}(\xi)$ which is the $(n-k-1)^{th}$ derivative of $p(\xi)$. Since $S_{k}(b)=S_{k+1}(b)=0$ for $k>0$, it follows that $\xi^{2}$ divides $p^{(n-k-1)}(\xi)$ and hence $\mathsf{mult}(p^{(n-k-1)},0)\geq 2$. Applying the above fact $n-k-1$ times, we get $\mathsf{mult}(p,0)\geq n-k+1$ so $S_{n}(b)=\ldots=S_{k}(b)=0$. ∎

Finally we discuss how to generate the $(k,\varepsilon)$-wise independent distributions on $[m]^{n}$ with seed length $O(\log\log(n)+k\log(m)+\log(1/\varepsilon))$. We claim that it suffices to take a $k^{\prime}=k\log(m)$-wise $\varepsilon$-independent string of length $n^{\prime}=n\log(m)$. Naor and Naor [NN93] showed that such distributions can be generated using seed-length $O(\log\log(n)+k\log(m)+\log(1/\varepsilon))$. We can also assume that every co-ordinate is uniformly random in $[m]$ by adding the string $(a,\ldots,a)$ where $a\in[m]$ is chosen randomly.