Bounded Independence Fools Degree-2 Threshold Functions

Introduction

A distribution $\mathcal{D}$ on $\{-1,1\}^{n}$ is said to $\varepsilon$-fool a function $f:\{-1,1\}^{n}\to\{-1,1\}$ if

where $\mathcal{U}$ is the uniform distribution on $\{-1,1\}^{n}$. A distribution $\mathcal{D}$ on $\{-1,1\}^{n}$ is $k$-wise independent if every restriction of $\mathcal{D}$ to $k$ coordinates is uniform on $\{-1,1\}^{k}$. Despite their simplicity, $k$-wise independent distributions have been a surprisingly powerful and versatile derandomization tool, fooling complex functions such as AC0 circuits and half-spaces . As a result, this class of distributions has played a fundamental role in many areas of theoretical computer science.

Our Results. The problem we study is the following: How large must $k=k(n,d,\varepsilon)$ be in order for every $k$-wise independent distribution on $\{-1,1\}^{n}$ to $\varepsilon$-fool the class of degree-$d$ PTF’s? The $d=1$ case of this problem was recently considered in , where it was shown that $k(n,1,\varepsilon)=\widetilde{\Theta}(1/\varepsilon^{2})$, independent of $n$, with an alternative proof to much of the argument given in . The main open problem in was to identify $k=k(n,d,\varepsilon)$ for $d\geq 2$. In this work, we make progress on this question by proving the following:

Prior to this work, no nontrivial result was known for $d>1$; it was not even known whether $o(n)$-wise independence suffices for constant $\varepsilon$. Using known constructions of $k$-wise independent distributions , Theorem 1.1 gives a large class of pseudo-random generators (PRGs) for degree-$2$ PTFs with seed length $\log(n)\cdot\widetilde{O}(\varepsilon^{-9})$.

Another consequence of Theorem 1.1 is that bounded independence suffices for the invariance principle of Mossell, O’Donnell, and Oleszkiewicz in the case degree-$2$ polynomials. Let $p(x)$ be an $n$-variate degree-$2$ multi-linear polynomial with “low influences”. The invariance principle roughly says that the distribution of $p$ is essentially invariant if $x$ is drawn from the uniform distribution on $\{-1,1\}^{n}$ versus the standard $n$-dimensional Gaussian distribution $\mathcal{N}(0,1)^{n}$. Our result implies that the $x$’s do not need to be fully independent for the invariance principle to apply, but that bounded independence suffices.

Motivation and Related Work. The literature is rich with explicit generators for various natural classes of functions. Recently, there has been much interest in not only constructing PRGs for natural complexity classes, but also in doing so with as broad and natural a family of PRGs as possible. One example is the recent work of Bazzi on fooling depth-$2$ circuits (simplified by Razborov ), and of Braverman on fooling AC0, with bounded independence Note that a PRG for AC0 with qualitatively similar – in fact slightly better – seed length had being already given by Nisan ..

In other recent and independent works, give PRGs for intersections of $m$ halfspaces (though not degree-$2$ threshold functions). The former has polynomial dependence on $m$ and requires only bounded independence as well (and considers other functions of halfspaces beside intersections), while the latter has poly-logarithmic dependence on $m$ under the Gaussian measure but is not solely via bounded independence. Our dependence on $m$ is polynomial.

Notation

Overview of our proof of Theorem 1.1

The program of our proof follows the outline of the proof in . We first prove that bounded independence fools the class of regular degree-$2$ PTF’s. We then reduce the general case to the regular case to show that bounded independence fools all degree-$2$ PTF’s. The bulk of our proof is to establish the first step; this is the most challenging part of this work and where our main technical contribution lies. The second step is achieved by adapting the recent results of .

We now elaborate on the first step. Let $f:\{-1,1\}^{n}\to\{-1,1\}$ be a boolean function. To show that $f$ is fooled by $k$-wise independence, it suffices – and is in fact necessary – to prove the existence of two degree-$k$ “sandwiching” polynomials $q_{u},q_{l}:\{-1,1\}^{n}\to\{-1,1\}$ that approximate $f$ in a certain technical sense (see e.g. ). Even though this is an $n$-dimensional approximation problem, it may be possible to exploit the additional structure of the function under consideration to reduce it to a low-dimensional problem. This is exactly what is done in both and for the case of regular halfspaces.

FT-mollification is a general procedure to obtain a smooth function with bounded derivatives that approximates some bounded function $f$. The univariate version of the method in the context of derandomization was introduced in . In this paper we generalize it to the multivariate setting and later use it to prove our main theorem.

2 Our Approach

The high-level argument is of similar flavor as the one outlined above for the case of halfspaces, but the details are more elaborate. The proof makes essential use of good tail bounds for $p_{1},p_{2}$, a new moment bound for $p_{3}$, properties of FT-mollification, and a variety of other tools such as the Invariance Principle and the anti-concentration bounds of .

Organization. Section 4 contains the results we will need on multivariate FT-mollification. In Section 5 we give our improved moment bound on quadratic forms. Section 6 contains the analysis of the regular case, and Section 7 concludes the proof of our main theorem. Section 8 summarizes our results on intersections.

Multivariate FT-mollification

Let $J$ be the Jacobian matrix corresponding to the change of variables from Cartesian to hyperspherical coordinates. Then

In this section we give several quantitative properties of FT-mollification. We start off with a few lemmas that will be useful later.

Proof. Since $B=\hat{b}^{2}$, the stated integral when $c=1$ is $\|\hat{b}\|_{2}^{2}$, which is $\|b\|_{2}^{2}=1$ by Plancherel’s theorem. For general $c$, make the change of variables $u=(cx_{1},\ldots,cx_{d})$ then integrate over $u$. $\blacksquare$

Eq. (4.1) follows by Cauchy-Schwarz. Eq. (4.2) follows from Plancherel’s theorem, since the Fourier transform of $\partial^{\alpha}\hat{b}$ is $x^{\alpha}\cdot b$, up to factors of $i$. Eq. (4.3) follows since $\|x^{\alpha}\cdot b\|_{2}\leq\|b\|_{2}=1$. Eq. (4.4) is seen combinatorially. Suppose we have $2d$ buckets $A_{i}^{j}$ for $(i,j)\in[d]\times$. We also have $|\beta|$ balls, with each having one of $d$ types with $\beta_{i}$ balls of type $i$. Then the number of ways to place balls into buckets such that balls of type $i$ only go into some $A_{i}^{j}$ is $2^{|\beta|}$ (each ball has $2$ choices). However, it is also $\sum_{\alpha\leq\beta}\binom{\beta}{\alpha}$, since for every placement of balls we must place some number $\alpha_{i}$ balls of type $i$ in $A_{i}^{1}$ and $\beta_{i}-\alpha_{i}$ balls in $A_{i}^{2}$. $\blacksquare$

Recalling that $B=\hat{b}^{2}$, the Fourier transform of $B$ is $(2\pi)^{-d/2}(b*b)$. The above integral is $(2\pi)^{d/2}$ times the Fourier transform of $x_{i}^{2}\cdot B$, evaluated at $0$. Since multiplying a function by $i\cdot x_{j}$ corresponds to partial differentiation by $x_{j}$ in the Fourier domain,

with the last equality using that $\frac{\partial}{\partial x_{i}}b$ is odd.

so that, after switching to hyperspherical coordinates,

The claim follows since $\|b\|_{2}^{2}=1$. $\blacksquare$

We conclude by observing that the above probability is simply

from which the lemma follows since $\mathbf{E}[\|x\|_{2}^{2}]=O(d^{2})$ by Claim 4.7. $\blacksquare$

with the last inequality holding by Lemma 4.5.

where Eq. (4.7) uses Lemma 4.4. $\blacksquare$

A spectral moment bound for quadratic forms

For a quadratic form $p(x)=\sum_{i\leq j}a_{i,j}x_{i}x_{j}$, we can associate a real symmetric matrix $A_{p}$ which has the $a_{i,i}$ on the diagonals and $a_{\min\{i,j\},\max\{i,j\}}/2$ on the offdiagonals, so that $p(x)=x^{T}A_{p}x$. We now show a moment bound for quadratic forms which takes into account the maximum eigenvalue of $A_{p}$. Our proof is partly inspired by a proof of Whittle , who showed the hypercontractive inequality for degree-$2$ polynomials when comparing $q$-norms to $2$-norms (see Theorem B.1).

Note if $\sum_{i\leq j}a_{i,j}^{2}\leq 1$ then $\|A_{p}\|_{\infty}\leq 1$, in which case our bound recovers a similar moment bound as the one obtained via hypercontractivity. Thus, in the special case of bounding $k$th moments of degree-$2$ polynomials against their $2$nd moment, our bound can be viewed as a generalization of the hypercontractive inequality (and of Whittle’s inequality).

We first give two lemmas. The first is implied by Khintchine’s inequality , and the second is a discrete analog of one of Whittle’s lemmas.

If $X,Y$ are independent with $\mathbf{E}[Y]=0$ and if $k\geq 2$, then $\mathbf{E}[|X|^{k}]\leq\mathbf{E}[|X-Y|^{k}]$.

We are now prepared to prove our Theorem 5.1.

Proof (of Theorem 5.1). Without loss of generality we can assume $\textrm{tr}(A)=0$. This is because if one considers $A^{\prime}=A-(\textrm{tr}(A)/n)\cdot I$, then $x^{T}Ax-\textrm{tr}(A)=x^{T}A^{\prime}x$, and we have $\|A^{\prime}\|_{2}\leq\|A\|_{2}$ and $\|A^{\prime}\|_{\infty}\leq 2\|A\|_{\infty}$. We now start by proving our theorem for $k$ a power of 2 by induction on $k$. For $k=2$, $\mathbf{E}[(x^{T}Ax)^{2}]=4\sum_{i<j}A_{i,j}^{2}$ and $\|A\|_{2}^{2}=\sum_{i}A_{i,i}^{2}+2\sum_{i<j}A_{i,j}^{2}$. Thus $\mathbf{E}[(x^{T}Ax)^{2}]\leq 2\|A\|_{2}^{2}$. Next we assume the statement of our Theorem for $k/2$ and attempt to prove it for $k$.

where $y\in\{-1,1\}^{n}$ is random and independent of $x$. Notice that if we swap $x_{i}$ with $y_{i}$ then $x+y$ remains constant as does $|x_{j}-y_{j}|$ and that $x_{i}-y_{i}$ is replaced by its negation. Consider averaging over all such swaps. Let $\xi_{i}=((x+y)^{T}A)_{i}$ and $\eta_{i}=x_{i}-y_{i}$. Let $z_{i}$ be $1$ if we did not swap and $-1$ if we did. Then $(x+y)^{T}A(x-y)=\sum_{i}\xi_{i}\eta_{i}z_{i}$. Averaging over all swaps,

The first inequality is by Lemma 5.2, and the second uses that $|\eta_{i}|\leq 2$. Note that

with the final inequality using Minkowski’s inequality (namely that $|\mathbf{E}[|X+Y|^{p}]|^{1/p}\leq|\mathbf{E}[|X|^{p}]|^{1/p}+|\mathbf{E}[|Y|^{p}]|^{1/p}$ for any random variables $X,Y$ and any $1\leq p<\infty$).

Next note $\|Ax\|_{2}^{2}=\langle Ax,Ax\rangle=x^{T}A^{2}x$. Let $B=A^{2}-\frac{\textrm{tr}(A^{2})}{n}I$. Then $\textrm{tr}(B)=0$. Also, $\|B\|_{2}\leq\|A\|_{2}\|A\|_{\infty}$ and $\|B\|_{\infty}\leq\|A\|_{\infty}^{2}$. The former holds since

The latter holds since the eigenvalues of $B$ are $\lambda_{i}^{2}-(\sum_{j=1}^{n}\lambda_{j}^{2})/n$ for each $i\in[n]$. The largest eigenvalue of $B$ is thus at most that of $A^{2}$, and since $\lambda_{i}^{2}\geq 0$, the smallest eigenvalue of $B$ cannot be smaller than $-\|A\|_{\infty}^{2}$.

Hence employing the inductive hypothesis on $B$ we have that

with the final equality holding since the middle term above is the geometric mean of the other two, and thus is dominated by at least one of them. This proves our hypothesis as long as $C\geq 64$.

To prove our statement for general $k$, set $k^{\prime}=2^{\left\lceil\log_{2}k\right\rceil}$. Then by the power mean inequality and our results for $k^{\prime}$ a power of $2$, $\mathbf{E}[|x^{T}Ax|^{k}]\leq(\mathbf{E}[|x^{T}Ax|^{k^{\prime}}])^{k/k^{\prime}}\leq 128^{k}\max\{\sqrt{k}\|A\|_{2},k\|A\|_{\infty}\}^{k}$. $\blacksquare$

Fooling regular degree-22 threshold functions

The main theorem of this section is the following.

For a quadratic form $f$ and random $x\in\{-1,1\}^{n}$,

with the absolute values unnecessary in the last inequality since $k$ is even. We now observe

since (a) every term in $P_{k-1}(M_{p}(X))$ is a monomial of degree at most $2k-2$ in the $X_{i}$, by evenness of $P_{k-1}$ in $x_{1},x_{2}$, and is thus determined by $2k$-independence, (b) $\sqrt{p_{1}(X)},\sqrt{p_{2}(X)}$ are real by positive semidefiniteness of $p_{1},p_{2}$ (note that we are only given that the high order partial derivatives are bounded by $O(\alpha^{k})$ on the reals; we have no guarantees for complex arguments), and (c) the moment expectations above are equal for $X$ and $Y$ since they are determined by $2k$-independence.

We now bound the error term above. We have

by Lemma 6.2, with the same bound holding for $\mathbf{E}[(p_{2}(X))^{k/2}]$. We also have

which is at most $\varepsilon$ for sufficiently large $B$ by our lower bounds on $k$ and $1/\delta$. $\blacksquare$

In proving Theorem 6.1, we will need a lemma which states that $p$ is anticoncentrated even when evaluated on Bernoulli random variables which are $k$-wise independent. To show this, we make use of the following lemma, which follows from the Invariance Principle, the hypercontractive inequality, and the anticoncentration bound of . The proof is in Section D.

We now prove our anticoncentration lemma in the case of limited independence.

Item (i) is straightforward from Theorem 4.8. For item (ii), note that if $x\in T_{t,\varepsilon^{\prime}}$, then $d_{2}(x,\partial S_{\rho,t,\varepsilon^{\prime}})\geq\rho$, implying

with the last inequality using that $d_{2}(x,T_{t,\varepsilon^{\prime}})\geq 2\rho$.

Noting $\mathbf{Pr}[|p(Z)-t|<\varepsilon^{\prime}]=\mathbf{E}[I_{T_{t,\varepsilon^{\prime}}}(M_{p}(Z))]$ for any random variable $Z=(Z_{1},\ldots,Z_{n})$, item (ii) tells us that

This is because by adding a vector $v$ to $x$, we can change each individual coordinate of $x$ by at most $\|v\|_{2}$, and can thus change the value of $|x_{1}^{2}-x_{2}^{2}+x_{3}+x_{4}+C+\Upsilon-t|-\varepsilon^{\prime}$ by at most $2\|v\|_{2}\cdot(|x_{1}|+|x_{2}|+1)+\|v\|_{2}^{2}$.

Now let $X\in\{-1,1\}^{n}$ be uniformly random. We thus have that, for any particular $w>0$,

with the last inequality holding by Lemma 6.4.

where $B>1$ is the sufficiently large constant in Lemma 6.3. Thus Eq. (6.4) is now $O(\sqrt{\varepsilon^{\prime}}+\tau^{1/9})$. (We remark that a different $\delta$ is used when proving Theorem 6.1.)

which does not affect any of our properties (i),(ii), (iii).

Now, by our choice of $k,\delta$ and item (i), we have by Lemma 6.3 (with $\alpha=2c$) that

This completes our proof by applying Eq. (6.2) with $Z=Y$. $\blacksquare$

The following Corollary is proven similarly as Lemma 6.4, but uses anticoncentration under bounded independence (which we just proved in Lemma 6.5). The proof is in Section D.

Let $\eta,\eta^{\prime}\geq 0$ be given, and let $Y_{1},\ldots,Y_{n}$ be $k$-independent Bernoulli for $k$ as in Lemma 6.5 with $\varepsilon^{\prime}=\min\{\eta/\sqrt{\delta},\eta^{\prime}\}$. Also assume $k\geq\left\lceil 2/\delta\right\rceil$. Then

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

We set $\rho=\varepsilon^{4}$, $c=1/\rho$, and $1/\delta=2Bc$ for $B$ the constant in the statement of Lemma 6.3. We now show a chain of inequalities to give our theorem:

by choice of $\rho,\delta$ and applications of Lemma 6.4.

since $\rho^{2}=o(\varepsilon^{2})$ (we only changed the second summand). To apply Corollary 6.6 to Eq. (6.6), we need $k\geq\left\lceil 2/\delta\right\rceil$, which is true, and $k=\Omega(1/(\varepsilon^{\prime\prime})^{4})$, for $\varepsilon^{\prime\prime}=\min\{\rho/\sqrt{\delta},\varepsilon^{2}\}=\varepsilon^{2}$, which is also true. Corollary 6.6 then tells us Eq. (6.6) is $O(\varepsilon+\tau^{1/9})$. $\blacksquare$

Our main theorem of this Section (Theorem 6.1) also holds under the case that the $X_{i},Y_{i}$ are standard normal, and without any error term depending on $\tau$. We give a proof in Section D.2, by reducing back to the Bernoulli case.

Reduction to the regular case

In this section, we complete the proof of Theorem 1.1. We accomplish this by providing a reduction from the general case to the regular case. In fact, such a reduction can be shown to hold for any degree $d\geq 1$ and establishes the following:

Suppose $K_{d}$-wise independence $\varepsilon$-fools the class of $\tau$-regular degree-$d$ PTF’s, for some parameter $0<\tau\leq\varepsilon$. Then $(K_{d}+L_{d})$-wise independence $\varepsilon$-fools all degree-$d$ PTFs, where $L_{d}=(1/\tau)\cdot\big(d\log(1/\tau)\big)^{O(d)}$.

Our proof of Theorem 7.1 is based on the above structural lemma. Under the uniform distribution, there is some particular distribution on the leaves (the tree is not of uniform height); then conditioned on the restricted variables the variables still undetermined at the leaf are still uniform. With $(K_{d}+L_{d})$-wise independence, a random walk down the tree arrives at each leaf with the same probability as in the uniform case (since the depth of the tree is at most $L_{d}$). Hence, the probability mass of the “bad” leaves is at most $\tau\leq\varepsilon$ even under bounded independence. Furthermore, the induced distribution on each leaf (over the unrestricted variables) is $K_{d}$-wise independent. Consider a good leaf. Either the leaf is $\tau$-regular, in which case we can apply Theorem 6.1, or it is $\tau$-close to a constant function. At this point though we arrive at a technical issue. The statement and proof in concerning “close-to-constant” leaves holds only under the uniform distribution. For our result, we need a stronger statement that holds under any distribution (on the variables that do not appear in the path) that has sufficiently large independence. By simple modifications of the proof in , we show that the statement holds even under $O(d\cdot\log(1/\tau))$-wise independence. $\blacksquare$

Fooling intersections of threshold functions

Our approach also implies that the intersection of halfspaces (or even degree-$2$ threshold functions) is fooled by bounded independence. While Theorem D.1 implies that $\Omega(\varepsilon^{-8})$-wise independence fools GW rounding, we can do much better by noting that to fool GW rounding it suffices to fool the intersection of two halfspaces under the Gaussian measure.

since the sum of such expectations over all edges $(u,v)$ gives us the expected number of edges that are cut (note equality holds above since the two halfspace intersections are disjoint). The following theorem then implies that to achieve a maximum cut within a factor $.878...-\varepsilon$ of optimal in expectation, it suffices that the entries of the random normal vector $r$ have entries that are $\Omega(1/\varepsilon^{2})$-wise independent. The proof of the theorem is in Section F.

Let $H_{1}=\{x:\left\langle a,x\right\rangle>\theta_{1}\}$ and $H_{2}=\{x:\left\langle b,x\right\rangle>\theta_{2}\}$ be two halfspaces, with $\|a\|_{2}=\|b\|_{2}=1$. Let $X,Y$ be $n$-dimensional vectors of standard normals with the $X_{i}$ independent and the $Y_{i}$ $k$-wise independent for $k=\Omega(1/\varepsilon^{2})$. Then $|\mathbf{Pr}[X\in H_{1}\cap H_{2}]-\mathbf{Pr}[Y\in H_{1}\cap H_{2}]|<\varepsilon.$

Acknowledgments

We thank Piotr Indyk and Rocco Servedio for comments that improved the presentation of this work. We also thank Ryan O’Donnell for bringing our attention to the problem of the intersection of threshold functions.

References

Appendix A Basic linear algebra facts

In this subsection we record some basic linear algebraic facts used in our proofs.

Note Fact A.1 and Fact A.2 imply the following.

The following standard result will be useful:

We now give a simple lemma that gives an upper bound on the magnitude of the trace of a symmetric matrix with positive eigenvalues.

Appendix B Useful facts about polynomials

Our first fact is a consequence of the well-known hypercontractivity theorem.

If $f$ is a degree-$d$ polynomial and $1\leq r<q\leq\infty$,

Our second fact is an anticoncentration theorem for low-degree polynomials over independent standard Gaussian random variables.

For $f$ a non-zero, $n$-variate, degree-$d$ polynomial,

The following is a statement of the Invariance Principle of Mossell, O’Donnell, and Oleszkiewicz , in the special case when the random variables $X_{i}$ are Bernoulli.

where the $G_{i}\sim\mathcal{N}(0,1)$ are independent.

The following tail bound argument is standard (see for example ). We repeat the argument here just to point out that only bounded independence is required.

If $f$ is a degree-$d$ polynomial, $t>8^{d/2}$, and $X$ is drawn at random from a $(dt^{2/d})$-wise independent distribution over $\{-1,1\}^{n}$, then

by Markov’s inequality. Set $k=2\cdot\left\lfloor t^{2/d}/4\right\rfloor$ and note $k>2$ as long as $t>8^{d/2}$. Now the right hand side of Eq. (B.1) is at most $2^{-dk/2}$, as desired. Finally, note independence was only used to bound $\mathbf{E}[|f(X)|^{k}]$, which for $k$ even equals $\mathbf{E}[f(X)^{k}]$ and is thus determined by $dk$-independence. $\blacksquare$

B.2 Facts about quadratic forms.

The following facts are concerned with quadratic forms, i.e. polynomials $p(x)=\sum_{i\leq j}a_{i,j}x_{i}x_{j}$. We often represent a quadratic form $p$ by its associated symmetric matrix $A_{p}$, where

The following is a bound on moments for quadratic forms.

Let $f(x)$ be a degree-$2$ polynomial. Then, for $X=(X_{1},\ldots,X_{n})$ a vector of independent Bernoullis,

Proof. Over the hypercube we can write $f=q+\textrm{tr}(A_{f})$ where $q$ is multilinear. Note $\|A_{q}\|_{2}\leq\|A_{f}\|_{2}$. Then by Theorem B.1,

The following corollary now follows from Theorem B.4 and Lemma A.6.

Proof. Write $f=g+C$ via Lemma A.6 with $0\leq C\leq 1/\delta$ and $g$ multilinear, $\|A_{g}\|_{2}\leq\|A_{f}\|_{2}\leq 1$. Apply Theorem B.4 to $g$ with $t=1/\delta$. $\blacksquare$

The following lemma gives a decomposition of any multi-linear quadratic form as a sum of quadratic forms with special properties for the associated matrices. It is used in the proof of Theorem 6.1.

Let $\delta>0$ be given. Let $f$ be a multilinear quadratic form. Then $f$ can be written as $f_{1}-f_{2}+f_{3}$ for quadratic forms $f_{1},f_{2},f_{3}$ where:

$\|A_{f_{1}}\|_{2},\|A_{f_{2}}\|_{2},\|A_{f_{3}}\|_{2}\leq\|A_{f}\|_{2}$.

Proof. Since $A_{f}$ is real and symmetric, we can find an orthogonal matrix $Q$ such that $\Lambda=Q^{T}A_{f}Q$ is diagonal. Each diagonal entry of $\Lambda$ is either at least $\delta$, at most $-\delta$, or in between. We create a matrix $P$ containing all entries of $\Lambda$ which are at least $\delta$, with the others zeroed out. We similarly create $N$ to have all entries at most $-\delta$. We place the remaining entries in $R$. We then set $A_{f_{1}}=QPQ^{T},A_{f_{2}}=QNQ^{T},A_{f_{3}}=QRQ^{T}$. Note $\|\Lambda\|_{2}^{2}=\|A_{f}\|_{2}^{2}$ by Fact A.3, so since we remove terms from $\Lambda$ form each $A_{f_{i}}$, their Frobenius norms can only shrink. The eigenvalue bounds hold by construction and Fact A.1. $\blacksquare$

Appendix C Why the previous approaches failed

In this section, we attempt to provide an explanation as to why the approaches of and fail to fool degree-$2$ PTFs.

The reason this fails is because the (tight) concentration properties of $p$ – as implied by hypercontractivity – are not sufficient for the analysis to bound the error of the approximation, even if we let the degree of the polynomial $P$ tend to infinity. (Paradoxically, the error coming from the worst-case analysis becomes worse as the degree of $P$ increases.)

C.2 Why the analysis for univariate FT-mollification failed

We discuss why the argument in failed to generalize to higher degree. Recall that the argument was via the following chain of inequalities:

Appendix D Proofs omitted from Section 6

We next give a proof of Lemma 6.4, where $p_{1},p_{2},\delta$ are as in Section 6 (recall $p=p_{1}-p_{2}+p_{3}+p_{4}+C$ where $p_{1},p_{2}$ are positive semidefinite with minimum non-zero eigenvalues at least $\delta$).

and similarly for $\sqrt{p_{2}(X)}$. We can thus bound our desired probability by

By Theorem B.2, together with Theorem B.3, we can bound the probability in the lemma statement by

Corollary 6.6 (restatement). Let $\eta,\eta^{\prime}\geq 0$ be given, and let $Y_{1},\ldots,Y_{n}$ be $k$-independent Bernoulli for $k$ as in Lemma 6.5 with $\varepsilon^{\prime}=\min\{\eta/\sqrt{\delta},\eta^{\prime}\}$. Also assume $k\geq\left\lceil 2/\delta\right\rceil$. Then

D.2 Gaussian Setting

In the following Theorem we show that the conclusion of Theorem 6.1 holds even under the Gaussian measure.

Let $0<\varepsilon<1$ be given. Let $G=(G_{1},\ldots,G_{n})$ be a vector of independent standard normal random variables, and $G^{\prime}=(G^{\prime}_{1},\ldots,G^{\prime}_{n})$ be a vector of $2k$-wise independent standard normal random variables for $k$ a sufficiently large multiple of $1/\varepsilon^{8}$. If $p(x)=\sum_{i\leq j}a_{i,j}x_{i}x_{j}$ has $\sum_{i\leq j}a_{i,j}^{2}=1$,

Now, we make the setting $\epsilon=\log^{1/3}(N)/\sqrt{N}$. By the Chernoff bound,

If $(1-\epsilon)N/2\leq k_{i}\leq(1+\epsilon)N/2$, then $|T_{k_{i},N}-T_{k_{i}+1,N}|=o(1)$.

Before proving the claim, we show how now we can use it to prove our Theorem. We argue by the following chain of inequalities:

We note $\sum_{i,j}a_{i,j}^{2}=1$, and thus $\sum_{i,j}|a_{i,j}|\leq n$ by Cauchy-Schwarz. We thus have that $|p^{\prime}(X)-p(G)|\leq\varepsilon^{2}$ with probability at least $1-\varepsilon^{2}$, and thus $|p^{\prime\prime}(X)-p(G)|\leq\varepsilon^{2}+|(\alpha-1)\cdot p(X)|$ with probability at least $1-\varepsilon^{2}$. We finally condition on the event $\mathcal{E}^{\prime\prime}$ that $|(\alpha-1)\cdot p^{\prime}(X)|\leq\varepsilon^{2}$. Since $p^{\prime}$ can be written as a multilinear quadratic form with sum of squared coefficients at most $1$, plus its trace $\textrm{tr}(A_{p^{\prime}})$ (which is $\sum_{i}a_{i,i}\leq\sqrt{n}$, by Cauchy-Schwarz), we have

which for large enough $N$ and the fact that $\|p^{\prime}\|_{2}=O(1+\textrm{tr}(A_{p^{\prime}}))$ irrespective of $N$, is at most

Proof (of Claim D.2). The claim is argued by showing that for $k_{i}$ sufficiently close to its expectation (which is $N/2$), the density function of the Gaussian (i.e. the derivative of its CDF) is sufficiently large that the distance we must move from $T_{k_{i},N}$ to $T_{k_{i}+1,N}$ to change the CDF by $\Theta(1/\sqrt{N})\geq 2^{-N}\binom{N}{k_{i}+1}$ is small. We argue the case $(1-\epsilon)N/2\leq k_{i}\leq N/2$ since the case $N/2\leq k_{i}\leq(1+\epsilon)N/2$ is argued symmetrically. Also, we consider only the case $k_{i}=(1-\epsilon)N/2$ exactly, since the magnitude of the standard normal density function is smallest in this case.

Observe that each $Z_{i}$ is a degree-$1$ polynomial in the $X_{i,j}$ with maximum influence $1/N$, and thus by the Berry-Esséen Theorem,

Note though for $t=\Theta(\log^{1/3}(N))$, the density function $f$ of the standard normal satisfies $f(t)=e^{-t^{2}/2}=N^{-o(1)}$. Thus, in this regime we can change the CDF by $\Theta(1/\sqrt{N})$ by moving only $N^{o(1)}/\sqrt{N}=o(1)$ along the real axis, implying $T_{k_{i}+1,N}-T_{k_{i},N}=o(1)$. $\blacksquare$

Appendix E Proofs from Section 7

We begin by stating the following structural lemma:

In the course of the proof we make repeated use of the following standard fact:

Let $\mathcal{D}$ be a $k$-wise independent distribution over $\{-1,1\}^{n}$. Condition on any fixed values for any $t\leq k$ bits of $\mathcal{D}$, and let $\mathcal{D}^{\prime}$ be the projection of $\mathcal{D}$ on the other $n-t$ bits. Then $\mathcal{D}^{\prime}$ is $(k-t)$-wise independent.

Throughout the proof, $\mathcal{D}$ denotes a $(K_{d}+L_{d})$-wise independent distribution over $\{-1,1\}^{n}$. Consider a random walk on the tree $\mathcal{T}$. Let $LD(\mathcal{T},\mathcal{D})$ (resp. $LD(\mathcal{T},\mathcal{U})$) be the leaf that the random walk will reach when the inputs are drawn from the distribution $\mathcal{D}$ (resp. the uniform distribution). The following straightforward lemma quantifies the intuition that these distributions are the same. This holds because the tree has small depth and $\mathcal{D}$ has sufficient independence.

For any leaf $\rho\in L(\mathcal{T})$ we have $\mathbf{Pr}\big[LD(\mathcal{T},\mathcal{D})=\rho\big]=\mathbf{Pr}\big[LD(\mathcal{T},\mathcal{U})=\rho\big].$

The following lemma says that, if $\rho$ is a good leaf, the distribution induced by $\mathcal{D}$ on $\rho$ $O(\varepsilon)$-fools the restricted subfunction $f_{\rho}$.

Let $\rho\in GL(\mathcal{T})$ be a good leaf and consider the projection $\mathcal{D}_{[n]\setminus\rho}$ of $\mathcal{D}$ on the variables not in $\rho$. Then we have $\big|\mathbf{Pr}_{x\sim\mathcal{D}_{[n]\setminus\rho}}[f_{\rho}(x)=1]-\mathbf{Pr}_{y\sim\mathcal{U}_{[n]\setminus\rho}}[f_{\rho}(y)=1]\big|\leq 2\varepsilon.$

Proof. If $f_{\rho}$ is $\tau$-regular, by Fact E.2 and recalling that $|\rho|\leq 0pt(d,\tau)\leq L_{d}$, the distribution $\mathcal{D}_{[n]\setminus\rho}$ is $K_{d}$-wise independent. Hence, the statement follows by assumption. Otherwise, $f_{\rho}$ is $\varepsilon$-close to a constant, i.e. there exists $b\in\{-1,1\}$ so that for any $t=O(d\log(1/\tau))$-wise distribution $\mathcal{D}^{\prime}$ over $\{-1,1\}^{n-|\rho|}$ we have $\mathbf{Pr}_{x\sim\mathcal{D}^{\prime}}[f_{\rho}(x)\neq b]\leq\tau$ $(*)$. Since $L_{d}>>t$, Fact E.2 implies that $(*)$ holds both under $\mathcal{D}_{[n]\setminus\rho}$ and $\mathcal{U}_{[n]\setminus\rho}$, hence the statement follows in this case also, recalling that $\tau\leq\varepsilon$. $\blacksquare$

The proof of Theorem 7.1 now follows by a simple averaging argument. By the decision-tree decomposition of Theorem E.1, we can write

where $\mathcal{D}^{\prime}$ is either $\mathcal{D}$ or the uniform distribution $\mathcal{U}$. By Theorem E.1 and Lemma E.3 it follows that the probability mass of the bad leaves is at most $\varepsilon$ under both distributions. Therefore, by Lemma E.3 and Lemma E.4 we get

E.2 Proof of Theorem E.1

In this section we provide the proof of Theorem E.1. For the sake of completeness, we give below the relevant machinery from . We note that over the hypercube every polynomial can be assumed to be multilinear, and so whenever we discuss a polynomial in this section it should be assumed to be multilinear. We start by defining the notion of the critical index of a polynomial:

If Eq. (E.1) does not hold for any $i$ we say that the $\tau$-critical index of $p$ is $+\infty.$ If $p$ is has $\tau$-critical index 0, we say that $p$ is $\tau$-regular.

If the $\tau$-critical index of $p$ is positive but not “very large”, then a random restriction of a “small” number of variables – the variables with largest influence in $p$ – causes $p$ to become “sufficiently” regular with probability $1/2^{O(d)}.$

Formally, we require the following lemma which is a strengthening of Lemma 10 in :

There exists a value $k\leq\alpha/\tau^{\prime}$, such that with probability at least $1/2^{O(d)}$ over a random restriction $\rho$ fixing the first $k$ variables of $p$, the polynomial $p_{\rho}$ is $\tau^{\prime\prime}$-regular.

By applying the above lemma in a recursive manner we obtain Theorem E.1. This is done exactly as in the proof of Theorem 1 in . We remark that in every recursive application of the lemma, the value of the parameter $\beta$ is set to $\tau$. This explains why $O(d\log(1/\tau))$-independence suffices in the second statement of Theorem E.1. Hence, to complete the proof of Theorem E.1, it suffices to establish Lemma E.6.

The proof of the second statement proceeds in two steps. Let $H$ denote the first $L^{\prime}$ most influential variables of $p$ and $T=[n]\setminus H$. Let $p^{\prime}(x_{H})=\sum_{S\subseteq H}\widehat{p}(S)x_{S}$. We first argue that with probability at least $2^{-\Omega(d)}$ over a random restriction $\rho$ to $H$, the restricted polynomial $p_{\rho}(x_{T})$ will have a “large” constant term $\widehat{p}_{\rho}(\emptyset)=p^{\prime}(\rho)$, in particular at least $\theta=2^{-\Omega(d)}$. The proof is based on the fact that, since the critical index is large, almost all of the Fourier weight of the polynomial $p$ lies in $p^{\prime}$, and it makes use of a certain anti-concentration property over the hypercube. Since the randomness is over $H$ and the projection of $\mathcal{D}$ on those variables is still uniform, the argument holds unchanged under $\mathcal{D}$.

This is done in using a concentration bound on the “tail”, assuming full independence. Thus, in this case, we need to modify the argument since the projection of $\mathcal{D}$ on the “tail” variables is not uniform. However, a careful inspection of the parameters reveals that the concentration bound needed above actually holds even under an assumption of $O(d\log(1/\beta))$-independence for the “tail” $x_{T}$. In particular, given the upper bound on $\|p_{\rho}-p^{\prime}_{\rho}\|_{2}$ and the lower bound on $\theta$, it suffices to apply Theorem B.4 for $t=\log(1/\beta)^{d/2}$, which only requires $(dt^{2/d})$-wise independence. Hence, we are done in this case too.

The proof of the third statement remains essentially unchanged for the following reason: One proceeds by considering a random restriction of the variables of $p$ up to the $\tau$-critical index – which in this case is small. Hence, the distribution induced by $\mathcal{D}$ on this space is still uniform. Since the randomness is over these “head” variables, all the arguments remain intact and the claim follows. $\blacksquare$

Appendix F Appendix to Section 8

We show a generalization of Theorem 8.1 to the intersection of $m>1$ halfspaces, which implies Theorem 8.1 as the special case $m=2$.

Theorem 8.1 (restatement). Let $m>1$ be an integer. Let $H_{i}=\{x:\left\langle a_{i},x\right\rangle>\theta_{i}\}$ for $i\in[m]$, with $\|a_{i}\|_{2}=1$ for all $i$. Let $X$ be a vector of $n$ i.i.d. Gaussians, and $Y$ be a vector of $k$-wise independent Gaussians. Then for $k=\Omega(m^{6}/\varepsilon^{2})$,

Note the maximum influence $\tau$ does not play a role since under the Gaussian measure we never need invoke the Invariance Principle. For the first inequality, observe $d_{2}(x,\partial R)\geq\min_{i}\{|x_{i}-\theta_{i}|\}$. Then by a union bound,

which is $O(mw)$ by Theorem B.2 with $d=1$. Now,

where Eq. (F.2) follows from Theorem 4.10.

The last inequality in Eq. (F.1) is argued identically, except that we need to have anticoncentration of the $|\left\langle a_{i},Y\right\rangle|$ in intervals of size no smaller than $\rho=\varepsilon/m$; this was already shown to hold under $O(1/\rho^{p})$-wise independence in [25, Lemma 2.5] for any $p$-stable distribution, and the Gaussian is $p$-stable for $p=2$.

with the inequality holding by Lemma 5.2, and the $m^{k}$ arising as the analogue of the $4^{k}$ term that arose in Eq. (6.1). This is at most $\varepsilon$ for $k$ a sufficiently large constant times $(cm)^{2}$, and thus overall $k=\Omega(m^{6}/\varepsilon^{2})$-wise independence suffices. $\blacksquare$

Several improvements are possible to reduce the dependence on $m$ in Theorem 8.1. We presented the simplest proof we are aware of which obtains a polynomial dependence on $m$, for clarity of exposition. See Section G.2 for an improvement on the dependence on $m$ to quartic.

Identical conclusions also hold for $X,Y$ being drawn from $\{-1,1\}^{n}$, since we can apply the decision tree argument from Theorem E.1 to each of the $m$ polynomial threshold functions separately so that, by a union bound, with probability at least $1-m\tau^{\prime}$ each of the $m$ PTF restrictions is either $\tau^{\prime}$-close to a constant function, or is $\tau^{\prime}$-regular. Thus for whatever setting of $\tau$ sufficed for the case $m=1$ ($\tau=\varepsilon^{2}$ for halfspaces and $\tau=\varepsilon^{9}$ for degree-$2$ threshold functions (Theorem 6.1)), we set $\tau^{\prime}=\tau/m$ then argue identically as before.

Appendix G Various Quantitative Improvements

In the main body of the paper, at various points we sacrificed proving sharper bounds in exchange for clarity of exposition. Here we discuss various quantitative improvements that can be made in our arguments.

We use the following fact, whose proof can be found in .

The following lemma is used in our sharpening of the upper bound on $\|\partial^{\beta}B\|_{1}$.

Using the fact that $\Gamma(z+1)=z\Gamma(z)$, we can rewrite these as

We thus have $W(0)-X(0)+Y(0)+Z(0)=\Omega(W(0)+Y(0)+Z(0))$. Since $2C_{d}(W(0)-X(0)+Y(0)+Z(0))/d=\|b\|_{2}^{2}=1$, it thus suffices to show that $(W(\alpha)+Y(\alpha)+Z(\alpha))/(W(0)+Y(0)+Z(0))\leq(\alpha!\cdot 2^{O(|\alpha|+d)})\cdot(|\alpha|+d)^{-|\alpha|}$ for general $\alpha$. This can be seen just by showing the desired inequality for $W(\alpha)/W(0)$, $Y(\alpha)/Y(0)$, and $Z(\alpha)/Z(0)$ separately. We do the calculation for $W(\alpha)/W(0)$ here; the others are similar.

Proof. The proof is nearly identical to the proof of Lemma 4.5. The difference is in our bound of $\|x^{\alpha}\cdot b\|_{2}$. In the proof of Lemma 4.5, we just used that $\|x^{\alpha}\cdot b\|_{2}\leq\|b\|_{2}=1$. However ,by Lemma G.2, we can obtain the sharper bound

We now have the following sharpening of item (i) from Theorem 4.8. Over high dimension, for some $\beta$ the improvement can be as large as a shrinking of our upper bound in Theorem 4.8 by a $d^{-|\beta|/2}$ factor (for example, when each $\beta_{i}$ is $|\beta|/d$).

G.2 Improvements to fooling the intersection of halfspaces

In the proof of Theorem 8.1 in Section F, we presented a proof showing that $\Omega(m^{6}/\varepsilon^{2})$-independence $\varepsilon$-fools the intersection of $m$ halfspaces under the Gaussian measure. In fact, this dependence on $m$ can be improved to quartic. One factor of $m$ is shaved by using the improved bound from Theorem G.4, and another factor of $m$ is shaved by a suitable change of basis. The argument used to shave the second factor of $m$ is specific to the Gaussian case, and does not carry over to the Bernoulli setting.

Let $m>1$ be an integer. Let $H_{i}=\{x:\left\langle a_{i},x\right\rangle>\theta_{i}\}$ for $i\in[m]$, with $\|a_{i}\|_{2}=1$ for all $i$. Let $X$ be a vector of $n$ independent standard normals, and $Y$ be a vector of $k$-wise independent Gaussians. Then for $k=\Omega(m^{4}/\varepsilon^{2})$ and even,

For the first inequality and last inequalities, since we performed an orthonormal change of basis the $F(X)_{i}$ remain independent standard normals, and we can reuse the same analysis from the proof of Theorem 8.1 without modification.

Since the $F(X)_{i}$ are independent standard normal random variables, $\sum_{i=1}^{m}F(X)_{i}^{2}$ follows a chi-squared distribution with $m$ degrees of freedom, and its $k/2$th moment is determined by $k$-wise independence, and thus

This finishes our proof, since by Eq. (G.3) the expected value of our Taylor error is

which is $O(\varepsilon)$ for $k=\Omega(c^{2})=\Omega(m^{4}/\varepsilon^{2})$. $\blacksquare$