#  Detecting Low-Degree Truncation

Anindya De University of Pennsylvania. Email<EMAIL_ADDRESS>Huan Li
University of Pennsylvania. Email<EMAIL_ADDRESS>Shivam Nadimpalli
Columbia University. Email<EMAIL_ADDRESS>Rocco A. Servedio Columbia
University. Email<EMAIL_ADDRESS>
###### Abstract

We consider the following basic, and very broad, statistical problem: Given a
known high-dimensional distribution ${\cal D}$ over $\mathbb{R}^{n}$ and a
collection of data points in $\mathbb{R}^{n}$, distinguish between the two
possibilities that (i) the data was drawn from ${\cal D}$, versus (ii) the
data was drawn from ${\cal D}|_{S}$, i.e. from ${\cal D}$ subject to
truncation by an unknown truncation set $S\subseteq\mathbb{R}^{n}$.

We study this problem in the setting where ${\cal D}$ is a high-dimensional
i.i.d. product distribution and $S$ is an unknown degree-$d$ _polynomial
threshold function_ (one of the most well-studied types of Boolean-valued
function over $\mathbb{R}^{n}$). Our main results are an efficient algorithm
when ${\cal D}$ is a _hypercontractive_ distribution, and a matching lower
bound:

  * •

For any constant $d$, we give a polynomial-time algorithm which successfully
distinguishes ${\cal D}$ from ${\cal D}|_{S}$ using $O(n^{d/2})$ samples
(subject to mild technical conditions on ${\cal D}$ and $S$);

  * •

Even for the simplest case of ${\cal D}$ being the uniform distribution over
$\\{-1,+1\\}^{n}$, we show that for any constant $d$, any distinguishing
algorithm for degree-$d$ polynomial threshold functions must use
$\Omega(n^{d/2})$ samples.

##  1 Introduction

One of the most basic and natural ways that a probability distribution ${\cal
D}$ can be altered is by _truncating_ it, i.e. conditioning on some subset of
possible outcomes. Indeed, the study of truncated distributions is one of the
oldest topics in probability and statistics: already in the 19th century,
Galton [Gal97] attempted to estimate the mean and standard deviation of the
running times of horses on the basis of sample data that did not include data
for horses that were slower than a particular cutoff value. Since the running
times were assumed to be normally distributed, this was an early attempt to
infer the parameters of an unknown normal distribution given samples from a
truncated version of the distribution. Subsequent early work by other
statistical pioneers applied the method of moments [Pea02, Lee14] and maximum
likehood techniques [Fis31] to the same problem of estimating the parameters
of an unknown univariate normal distribution from truncated samples. The study
of truncation continues to be an active area in contemporary statistics (see
[Sch86, BC14, Coh16] for recent books on this topic).

Quite recently, a number of research works in theoretical computer science
have tackled various algorithmic problems that deal with _high-dimensional_
truncated data. Much of this work attempts to _learn_ a parametric description
of an unknown distribution that has been subject to truncation. For example,
in [DGTZ19] Daskalakis, Gouleakis, Tzamos and Zampetakis gave an efficient
algorithm for high-dimensional truncated linear regression, and in [DGTZ18]
Daskalakis, Gouleakis, Tzamos and Zampetakis gave an efficient algorithm for
estimating the mean and covariance of an unknown multivariate normal
distribution from truncated samples given access to a membership oracle for
the truncation set. In [FKT20] Fotakis, Kalavasis and Tzamos gave a similar
result for the setting in which the unknown background distribution is a
product distribution over $\\{0,1\\}^{d}$ instead of a multivariate normal
distribution, and in [KTZ19] Kontonis, Tzamos and Zampetakis extended the
results of [DGTZ18] to the case of an unknown truncation set satisfying
certain restrictions. In summary, the recent work described above has focused
on learning (parameter estimation) of truncated normal distributions and
product distributions over $\\{0,1\\}^{d}.$

This Work: _Detecting_ Truncation. In the current paper, rather than the
learning problem we study what is arguably the most basic problem that can be
considered in the context of truncated data — namely, detecting whether or not
truncation has taken place at all. A moment’s thought shows that some
assumptions are required in order for this problem to make sense: for example,
if the truncation set is allowed to be arbitrarily tiny (so that only an
arbitrarily small fraction of the distribution is discarded by truncation),
then it can be arbitrarily difficult to detect whether truncation has taken
place. It is also easy to see that truncation cannot be detected if the
unknown truncation set is allowed to be arbitrarily complex. Thus, it is
natural to consider a problem formulation in which there is a fixed class of
possibilities for the unknown truncation set; this is the setting we consider.

We note that the truncation detection problem we consider has a high-level
resemblance to the standard _hypothesis testing_ paradigm in statistics, in
which the goal is to distinguish between a “null hypothesis” and an “alternate
hypothesis.” In our setting the null hypothesis corresponds to no truncation
of the known distribution having taken place, and the alternate hypothesis is
that the known distribution has been truncated by some unknown truncation set
belonging to the fixed class of possibilities. However, there does not appear
to be work in the statistics literature which deals with the particular kinds
of truncation problems considered in this work, let alone computationally
efficient algorithms for those problems.

Prior Work: Convex Truncation of Normal Distributions. Recent work [DNS23]
considered the truncation detection problem in a setting where the background
distribution ${\cal D}$ is the standard multidimensional normal distribution
$N(0,1)^{n}$ and the truncation set is assumed to be an unknown _convex set_
in $\mathbb{R}^{n}$. This specific problem formulation enabled the use of a
variety of sophisticated tools and results from high-dimensional convex
geometry, such as Gaussian isoperimetry and the Brascamp-Lieb inequality
[BL76b] and extensions thereof due to Vempala [Vem10]. Using these tools,
[DNS23] gave several different algorithmic results and lower bounds. Chief
among these were (i) a polynomial-time algorithm that uses
$O(n/\varepsilon^{2})$ samples and distinguishes the non-truncated standard
normal distribution $N(0,1)^{n}$ from $N(0,1)^{n}$ conditioned on a convex set
of Gaussian volume at most $1-\varepsilon$; and (ii) a
$\tilde{\Omega}(\sqrt{n})$-sample lower bound for detecting truncation by a
convex set of constant volume.

The results of [DNS23] provide a “proof of concept” that in sufficiently well-
structured settings it can sometimes be possible to detect truncation in a
computationally and statistically efficient way. This serves as an invitation
for a more general study of truncation detection; in particular, it is natural
to ask whether strong structural or geometric assumptions like those made in
[DNS23] (normal distribution, a convex truncation set) are required in order
to achieve nontrivial algorithmic results. Can efficient algorithms detect
truncation for broader classes of “background” distributions beyond the
standard normal distribution, or for other natural families of truncations
besides convex sets? This question is the motivation for the current work.

This Work: “Low-Degree” Truncation of Hypercontractive Product Distributions.
In this paper we consider

  * •

A broader range of possibilities for the background distribution ${\cal D}$
over $\mathbb{R}^{n}$, encompassing many distributions which may be either
continuous or discrete; and

  * •

A family of non-convex truncation sets corresponding to _low-degree polynomial
threshold functions_.

Recall that a Boolean-valued function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ is a _degree- $d$ polynomial threshold
function_ (PTF) if there is a real multivariate polynomial $p(x)$ with
$\deg(p)\leq d$ such that $f(x)=1$ if and only if $p(x)\geq 0.$ Low-degree
polynomial threshold functions are a well-studied class of Boolean-valued
functions which arise naturally in diverse fields such as computational
complexity, computational learning theory, and unconditional derandomization,
see e.g. [BS92, GL94, HKM14, DRST14, Kan14a, DOSW11, CDS20, DKPZ21, BHYY22,
DKN10, Kan11b, Kan11a, Kan12, KM13, MZ13, Kan14b, DDS14, DS14, Kan15, KKL17,
KL18, KR18, ST18, BV19, OST20] among many other references.

Our main results, described in the next subsection, are efficient algorithms
and matching information-theoretic lower bounds for detecting truncation by
low-degree polynomial threshold functions for a wide range of background
distributions and parameter settings.

###  1.1 Our Results

To set the stage for our algorithmic results, we begin with the following
observation:

######  Observation 1.

For any fixed (“known”) background distribution ${\cal P}$ over
$\mathbb{R}^{n}$, $O_{d}(n^{d}/\varepsilon^{2})$ samples from an unknown
distribution ${\cal D}$ are sufficient to distinguish (with high probability)
between the two cases that (i) ${\cal D}$ is the original distribution ${\cal
P}$, versus (ii) ${\cal D}$ is ${\cal P}|_{f}$, i.e. ${\cal P}$ conditioned on
$f^{-1}(1)$, where $f$ is an unknown degree-$d$ PTF satisfying
$\operatorname{{\bf Pr}}_{\boldsymbol{x}\sim{\cal P}}[f(\boldsymbol{x})=1]\leq
1-\varepsilon$.

This is an easy consequence of a standard uniform convergence argument using
the well-known fact that the Vapnik-Chervonenkis dimension of the class of all
degree-$d$ polynomial threshold functions over $\mathbb{R}^{n}$ is $O(n^{d})$.
For the sake of completeness, we give a proof in Appendix A.

While the above observation works for any fixed background distribution ${\cal
P}$, several drawbacks are immediately apparent. One is that a sample
complexity of $O(n^{d})$ is quite high, in fact high enough to information-
theoretically learn an unknown degree-$d$ PTF; are this many samples actually
required for the much more modest goal of merely _detecting_ whether
truncation has taken place? A second and potentially more significant issue is
that the above VC-based algorithm is computationally highly inefficient,
involving a brute-force enumeration over “all” degree-$d$ PTFs; for a sense of
how costly this may be, recall that even in the simple discrete setting of the
uniform distribution over the Boolean cube $\\{-1,1\\}^{n}$ there are
$2^{\Omega(n^{d+1})}$ distinct degree-$d$ PTFs over $\\{-1,1\\}^{n}$ for
constant $d$ [Sak93, Theorem 2.34]. So it is natural to ask whether there
exist more efficient (either in terms of running time or sample complexity)
algorithms for interesting cases of the truncation detection problem, and to
ask about lower bounds for this problem.

On the lower bounds side, it is natural to first consider arguably the
simplest case, in which ${\cal P}$ is the uniform distribution ${\cal U}$ over
the Boolean hypercube $\\{-1,+1\\}^{n}$. In this setting we have the following
observation:

######  Observation 2.

If the truncating PTF $f$ is permitted to have as few as $n^{d/2}$ satisfying
assignments, then any algorithm that correctly decides whether its samples
come from ${\cal D}={\cal U}$ versus from ${\cal D}={\cal U}|_{f}$ must use
$\Omega(n^{d/4})$ samples.

This lower bound can be established using only basic linear algebra and simple
probabilistic arguments; it is inspired by the “voting polynomials” lower
bound of Aspnes et al. [ABFR94] against $\mathsf{MAJ}$-of-$\mathsf{AC}^{0}$
circuits. We give the argument in Appendix B.

Taken together, there is a quartic gap between the (computationally
inefficient) upper bound given by 1 and the information-theoretic lower bound
of 2 for PTFs with extremely few satisfying assignments. Our main result is a
proof that the true complexity of the truncation distinguishing problem lies
exactly in the middle of these two extremes. We

  * (i)

Give a _computationally efficient_ distinguishing algorithm which has sample
complexity $O(n^{d/2})$ for a wide range of product distributions and values
of $\mathrm{Vol}(f)$, and

  * (ii)

Show that even for the uniform background distribution ${\cal U}$ over
$\\{-1,+1\\}^{n}$, distinguishing whether or not ${\cal U}$ has been truncated
by a degree-$d$ PTF of volume $\approx 1/2$ requires $\Omega(n^{d/2})$
samples.

We now describe our results in more detail.

An Efficient Algorithm. We give a truncation distinguishing algorithm which
succeeds if ${\cal P}$ is any multivariate i.i.d. product distribution ${\cal
P}=\mu^{\otimes n}$ over $\mathbb{R}^{n}$ satisfying a natural
_hypercontractivity_ property and if $\mathrm{Vol}(f)$ is “not too small.” We
defer the precise technical definition of the (fairly standard)
hypercontractivity property that we require to Section 2.2, and here merely
remark that a wide range of i.i.d. product distributions satisfy the required
condition, including the cases where $\mu$ is

  * •

any fixed distribution over $\mathbb{R}$ that is supported on a finite
(independent of $n$) number of points;

  * •

any normal distribution $N(c,\sigma^{2})$ where $c,\sigma$ are independent of
$n$;

  * •

any uniform distribution over a continuous interval $[a,b]$;

  * •

any distribution which is supported on an interval $[a,b]$ for which there are
two constants $0<c<C$ such that everywhere on $[a,b]$ the pdf is between
$c/(b-a)$ and $C/(b-a)$.

An informal statement of our main positive result is below:

######  Theorem 3 (Efficiently detecting PTF truncation, informal theorem
statement).

Let $0<\varepsilon<1$. Fix any constant $d$ and any hypercontractive i.i.d.
product distribution $\mu^{\otimes n}$ over $\mathbb{R}^{n}$. Let
$f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ be an
unknown degree-$d$ PTF such that

$1-\varepsilon\geq\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}[f(\boldsymbol{x})=1]\geq 2^{-O(\sqrt{n})}.$

There is an efficient algorithm that uses $\Theta(n^{d/2}/\varepsilon^{2})$
samples from ${\cal D}$ and successfully (w.h.p.) distinguishes between the
following two cases:

  1. (i)

${\cal D}$ is $\mu^{\otimes n}$, i.e. the “un-truncated” distribution; versus

  2. (ii)

${\cal D}$ is $\mu^{\otimes n}|_{f}$, i.e. $\mu^{\otimes n}$ truncated by $f$.

Note that $\varepsilon$ is a lower bound on the probability mass of the
distribution $\mu^{\otimes n}$ which has been “truncated;” as remarked
earlier, without a lower bound on $\varepsilon$, it can be arbitrarily
difficult to distinguish the truncated distribution. Thus, as long as the
background distribution is a “nice” i.i.d. product distribution and the
truncating PTF’s volume is “not too tiny”, in polynomial time we can achieve a
square-root improvement in sample complexity over the naive brute-force
computationally inefficient algorithm.

A Matching Lower Bound. It is natural to wonder whether Theorem 3 is optimal:
can we establish lower bounds on the sample complexity of determining whether
a “nice” distribution has been truncated by a PTF? And can we do this when the
truncating PTF (unlike in 2) has volume which is not extremely small?

Our main lower bound achieves these goals; it shows that even for the uniform
distribution ${\cal U}$ over $\\{-1,1\\}^{n}$ and for PTFs of volume $\approx
1/2$, the sample complexity achieved by our algorithm in Theorem 3 is best
possible up to constant factors.

######  Theorem 4 (Lower bound for detecting PTF truncation, informal theorem
statement).

Fix any constant $d$. Let $f\mathrel{\mathop{\mathchar
58\relax}}\\{-1,1\\}^{n}\to\mathbb{R}$ be an unknown degree-$d$ PTF such that
$\operatorname{{\bf Pr}}_{\boldsymbol{x}\sim{\cal
U}}[f(\boldsymbol{x})=1]\in[0.49,0.51].$ Any algorithm that uses samples from
${\cal D}$ and successfully (w.h.p.) distinguishes between the cases that (i)
${\cal D}$ is ${\cal U}$, versus (ii) ${\cal D}$ is ${\cal U}|_{f}$, must use
$\Omega(n^{d/2})$ samples.

###  1.2 Techniques

We now give a technical overview of both the upper bound (Theorem 3) and the
lower bound (Theorem 4), starting with the former.

####  1.2.1 Overview of Theorem 3

For simplicity, we start by considering the case when the background
distribution $\mathcal{P}=\mu^{\otimes n}$ is the uniform measure on the
Boolean hypercube.

The Boolean Hypercube $\\{-1,+1\\}^{n}$. Let us denote the uniform measure
over $\\{-1,+1\\}^{n}$ by $\mathcal{U}_{n}$. Recall that our goal is to design
an algorithm with the following performance guarantee: Given i.i.d. sample
access to an unknown distribution $\mathcal{D}$, the algorithm w.h.p.

  * (i)

Outputs “un-truncated” when $\mathcal{D}=\mathcal{U}_{n}$; and

  * (ii)

Outputs “truncated” when $\mathcal{D}=\mathcal{U}_{n}\mid_{f^{-1}(1)}$ for a
degree-$d$ PTF $f\mathrel{\mathop{\mathchar
58\relax}}\\{-1,+1\\}^{n}\to\\{0,1\\}$, where
$1-\varepsilon\geq\operatorname{{\bf Pr}}[f(\boldsymbol{x})=1]$ for
$\boldsymbol{x}\sim\mathcal{U}_{n}$.

To avoid proliferation of parameters, we set $\varepsilon=0.1$ for the rest of
the discussion. We thus have

$\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\mathcal{U}_{n}}{\left[f(\boldsymbol{x})=1\right]}\leq
0.9.$

For any point $x\in\\{-1,+1\\}^{n}$, let
$\widetilde{x}\in\\{-1,+1\\}^{{n\choose 1}+\ldots+{n\choose d}}$ be the vector
given by

$\widetilde{x}\mathrel{\mathop{\mathchar
58\relax}}={\left(\widetilde{x}_{\alpha}\right)}_{\begin{subarray}{c}\alpha\subseteq[n]\\\
0<|\alpha|\leq
d\end{subarray}}\qquad\text{where~{}}\widetilde{x}_{\alpha}\mathrel{\mathop{\mathchar
58\relax}}=\prod_{i\in\alpha}x_{i}.$

In other words, every coordinate of $\widetilde{x}$ corresponds to a non-
constant monomial in $x$ of (multilinear) degree at most $d$. Note that the
map $x\mapsto\widetilde{x}$ can be viewed as a _feature map_ corresponding to
the “polynomial kernel” in learning theory.

The main idea underlying our algorithm, which is given in Theorem 3, is the
following:

  1. 1.

When $\mathcal{D}=\mathcal{U}_{n}$, then it is easy to see that $\mathop{{\bf
E}\/}{\left[\widetilde{\boldsymbol{x}}\right]}=\overline{0}$ (the all-$0$
vector). This is immediate from the fact that the expectation of any non-
constant monomial under $\mathcal{U}_{n}$ is $0$.

  2. 2.

On the other hand, suppose $\mathcal{D}=\mathcal{U}_{n}\mid_{f^{-1}(1)}$ for a
degree-$d$ PTF $f$ as above. In this case, it can be shown that

${\left\|\mathop{{\bf
E}\/}_{\mathcal{U}_{n}\mid_{f^{-1}(1)}}\big{[}\widetilde{\boldsymbol{x}}\big{]}\right\|}_{2}\geq
2^{-\Theta(d)}=\mathrel{\mathop{\mathchar 58\relax}}c_{d}.$

This is done by relating the quantity in the LHS above to the Fourier spectrum
of degree-$d$ PTFs, which has been extensively studied in concrete complexity
theory (see for example [GL94, DRST14, HKM14, Kan13]). In particular, we
obtain this lower bound on ${\left\|\mathop{{\bf
E}\/}\left[\widetilde{\boldsymbol{x}}\right]\right\|}_{2}$ from an anti-
concentration property of low-degree polynomials over the Boolean hypercube.
This in turn is a consequence of hypercontractivity of the uniform measure
over $\\{-1,+1\\}^{n}$, a fundamental tool in discrete Fourier analysis (see
Section 9.5 of [O’D14]).

Items 1 and 2 above together imply that estimating ${\left\|\mathop{{\bf
E}\/}{\left[\widetilde{\boldsymbol{x}}\right]}\right\|}_{2}^{2}$ up to an
additive error of $\pm c_{d}^{2}/2$ suffices to distinguish between
$\mathcal{D}=\mathcal{U}_{n}$ and
$\mathcal{D}=\mathcal{U}_{n}\mid_{f^{-1}(1)}$. Next, note that

${\left\|\mathop{{\bf
E}\/}_{\mathcal{D}}\big{[}\widetilde{\boldsymbol{x}}\big{]}\right\|}_{2}^{2}=\mathop{{\bf
E}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\mathcal{D}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}\right]}.$

Using the idea of “U-statistics” [Hoe94], this suggests a natural unbiased
estimator, namely drawing $2T$ points
$\widetilde{\boldsymbol{x}}^{(1)},\ldots,\widetilde{\boldsymbol{x}}^{(T)}$ and
$\widetilde{\boldsymbol{y}}^{(1)},\ldots,\widetilde{\boldsymbol{y}}^{(T)}$ for
some $T$ which we will fix later, and then setting

$\mathbf{M}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{T^{2}}{\left\langle\sum_{i=1}^{T}\widetilde{\boldsymbol{x}}^{(i)},\sum_{j=1}^{T}\widetilde{\boldsymbol{y}}^{(j)}\right\rangle}.$

In particular, we have $\mathop{{\bf E}\/}[\mathbf{M}]={\left\|\mathop{{\bf
E}\/}{\left[\widetilde{\boldsymbol{x}}\right]}\right\|}_{2}^{2}$.

In order to be able to distinguish between the un-truncated and truncated
distributions by estimating $\mathbf{M}$ (and then appealing to Chebyshev’s
inequality), it therefore suffices to upper bound the variance of $\mathbf{M}$
in both the un-truncated and the truncated settings. When
$\mathcal{D}=\mathcal{U}_{n}$, then $\operatorname{{\bf Var}}[\mathbf{M}]$ is
straightforward to calculate and it turns out that

$\mathop{{\bf
Var}\/}_{\mathcal{U}_{n}}[\mathbf{M}]=\frac{m}{T^{2}}\qquad\text{where~{}}m\mathrel{\mathop{\mathchar
58\relax}}=\\#\\{\alpha\subseteq[n]\mathrel{\mathop{\mathchar
58\relax}}0<|\alpha|\leq d\\}=O_{d}(n^{d}).$

However, in the truncated setting, $\operatorname{{\bf Var}}[\mathbf{M}]$ is
significantly trickier to analyze; at a high-level, our analysis expresses
$\operatorname{{\bf Var}}[\mathbf{M}]$ in terms of the “weights” of various
levels of the Fourier spectrum of $f$.111See Section 2.1 for a formal
definition. The key technical ingredient we use to control the variance is the
so-called “level-$k$ inequality” for Boolean functions, which states that for
any Boolean function $f\mathrel{\mathop{\mathchar
58\relax}}\\{-1,+1\\}^{n}\to\\{0,1\\}$, writing $\mathbf{W}^{=k}[f]$ for the
“Fourier weight at level-$k$”, we have

$\mathbf{W}^{=k}[f]\leq
O_{k}{\left(\mathbf{W}^{=0}[f]\cdot\log^{k}{\left(\frac{1}{\mathbf{W}^{=0}[f]}\right)}\right)}.$

Recall that $\mathbf{W}^{=0}[f]=\mathop{{\bf E}\/}_{\mathcal{U}_{n}}[f]^{2}$,
and so the level-$k$ inequality bounds higher-level Fourier weight in terms of
the mean of the function. We remark that the level-$k$ inequality is also a
consequence of hypercontractivity over the Boolean hypercube (as before, see
Section 9.5 of [O’D14]). With this in hand, we can show that

$\mathop{{\bf
Var}\/}_{\mathcal{U}_{n}\mid_{f^{-1}(1)}}[\mathbf{M}]=\frac{O_{d}(n^{d})}{T^{2}}$

as long as $\mathop{{\bf E}\/}_{\mathcal{U}_{n}}[f]\geq 2^{-\sqrt{n}}$.

Finally, taking $T=\Theta_{d}(n^{d/2})$ implies that the standard deviation of
each of our estimators is comparable to the difference in means (which was
$c_{d}^{2}$), allowing us to distinguish between the un-truncated and
truncated settings.

Hypercontractive Product Distributions $\mu^{\otimes n}$. We use the same
high-level approach (as well as the same estimator $\mathbf{M}$) in order to
distinguish low-degree truncation of a hypercontractive product measure
$\mu^{\otimes n}$, but the analysis becomes more technically involved. To
explain the principal challenge, note that over the Boolean hypercube
$\\{-1,+1\\}^{n}$, the Fourier basis functions
$(\chi_{\alpha})_{\alpha\subseteq[n]},$

$\chi_{\alpha}(x)\mathrel{\mathop{\mathchar
58\relax}}=\prod_{i\in\alpha}x_{i},$

form a multiplicative group. This group structure is useful because it means
that the product of two basis functions is another basis function: For
$\alpha,\beta\subseteq[n]$, we have the product formula

$\chi_{\alpha}\cdot\chi_{\beta}=\chi_{\alpha\,\triangle\,\beta}$

where $\alpha\,\triangle\,\beta$ denotes the symmetric difference of $\alpha$
and $\beta$.

Over an arbitrary hypercontractive measure $\mu^{\otimes n}$, this may no
longer be the case; as a concrete example, this fails for the Gaussian measure
and the Hermite basis (cf. Chapter 11 of [O’D14]). Over a general product
space $\mu^{\otimes n}$ the Fourier basis functions are now indexed by _multi-
subsets_ of $[n]$ (as opposed to subsets of $[n]$ over $\\{-1,+1\\}^{n}$)—see
the discussion following Definition 5. More importantly, there is no simple
formula for the product of two Fourier basis functions, and this makes the
analysis technically more involved. We remark that this problem, which is
known as the _linearization problem_ , has been well studied for various
classes of orthogonal polynomials (see Section 6.8 of [AAR99]). Lemmas 17 and
16 establish a weak version of a “product formula” between two Fourier basis
functions for $\mu^{\otimes n}$ that suffices for our purposes and lets us
carry out an analysis similar to the above sketch for the Boolean hypercube
$\\{-1,+1\\}^{n}$.

####  1.2.2 Overview of Theorem 4

We turn to an overview of our lower bound, Theorem 4. As in the previous
section, we write $\mathcal{U}_{n}$ to denote the uniform distribution over
the $n$-dimensional Boolean hypercube $\\{-1,+1\\}^{n}$ and $(\chi_{S})_{S}$
for the Fourier basis over $\\{-1,+1\\}^{n}$. To prove Theorem 4, it suffices
to construct a distribution ${\cal F}_{d}$ over degree-$d$ PTFs over
$\\{-1,+1\\}^{n}$ with the following properties:

  1. 1.

The distribution ${\cal F}_{d}$ is supported on thresholds of homogenous
degree-$d$ polynomials over $\\{-1,+1\\}^{n}$. Note that such polynomials are
necessarily multilinear; in particular, each PTF $\boldsymbol{f}\sim{\cal
F}_{d}$ can be expressed as

$\boldsymbol{f}(x)\mathrel{\mathop{\mathchar
58\relax}}=\mathbf{1}{\left\\{\sum_{S\mathrel{\mathop{\mathchar
58\relax}}|S|=d}\widehat{\boldsymbol{p}}(S)\chi_{S}(x)\geq 0\right\\}}.$

The coefficients $\widehat{\boldsymbol{p}}(S)$ will be i.i.d. random variables
drawn from the standard Gaussian distribution $N(0,1)$.

  2. 2.

Let $m=\Omega(n^{d/2})$ and consider the distributions

     * •

$\mathcal{D}_{1}$, obtained by drawing $m$ independent samples from
$\mathcal{U}_{n}$; and

     * •

$\mathcal{D}_{2}$, obtained by first drawing
$\boldsymbol{f}\sim\mathcal{F}_{d}$, and then drawing $m$ independent samples
from $\mathcal{U}_{n}\mid_{\boldsymbol{f}^{-1}(1)}$.

Then distributions $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ are $o(1)$-close to
each other in variation distance.

Polynomials of the form

$\sum_{S}\widehat{\boldsymbol{p}}(S)\chi_{S}(x)\qquad\text{for}~{}\widehat{\boldsymbol{p}}(S)\sim
N(0,1)$

are known in the literature as _Gaussian random polynomials_ , and have been
extensively studied (with an emphasis on the behavior of their roots) [IZ97,
Ham56, BS14]. We will however be interested in a certain “pseudorandom-type”
behavior of these polynomials.

In particular, we first reduce the problem of proving indistinguishability of
${\cal D}_{1}$ and ${\cal D}_{2}$ to proving the following: Suppose
${\boldsymbol{u}}_{1},\ldots,{\boldsymbol{u}}_{m}$ are $m$ randomly chosen
points from $\\{-1,1\\}^{n}$ (which we fix). Then, with probability $1-o(1)$
over the choice of these $m$ points, the distribution of

${\left(\boldsymbol{f}(\boldsymbol{u}_{1}),\dots,\boldsymbol{f}(\boldsymbol{u}_{m})\right)}\qquad\text{is
$o(1)$-close to that
of}\qquad{\left(\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{m}\right)}$

for $\boldsymbol{f}\sim\mathcal{F}_{d}$ and where each $\boldsymbol{b}_{i}$ is
an independent unbiased random bit. In other words, we aim to show that if the
evaluation points $\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{m}$ are randomly
chosen (but subsequently known to the algorithm), then
$\boldsymbol{f}(\boldsymbol{u}_{1}),\dots,\boldsymbol{f}(\boldsymbol{u}_{m})$
is $o(1)$-indistinguishable from random.

We establish this last statement by proving something even stronger. Namely,
we first observe that the $\mathbb{R}^{m}$-valued random variable
$(\boldsymbol{p}(\boldsymbol{u}_{m}),\ldots,\boldsymbol{p}(\boldsymbol{u}_{m}))$
is an $m$-dimensional normal random variable for any fixed outcome of
$\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{m}$. Subsequently, we show that
this random variable
$(\boldsymbol{p}(\boldsymbol{u}_{m}),\ldots,\boldsymbol{p}(\boldsymbol{u}_{m}))$
is $o(1)$-close to the standard $m$-dimensional normal random variable
$N(0,I_{m})$ where $I_{m}$ is the identity matrix in $m$ dimensions. This
exploits a recent bound on total variation distance between multivariate
normal distributions [DMR20] in terms of their covariance matrices, and
involves bounding the trace of the Gram matrix generated by random points on
the hypercube; details are deferred to the main body of the paper.

###  1.3 Related Work

As mentioned earlier, “truncated statistics” has been a topic of central
interest to statisticians for more than a century and recently in theoretical
computer science as well. Starting with the work of Daskalakis et al.
[DGTZ18], several works have looked at the problem of learning an unknown
high-dimensional distribution in settings where the algorithm only gets
samples from a truncated set [FKT20, KTZ19, BDNP21]. We note here that in the
recent past, there have also been several works on truncation in the area of
statistics related to supervised learning scenarios [DSYZ21, DGTZ19, DRZ20],
but the models and techniques in those works are somewhat distant from the
topic of the current paper. Finally, in retrospect, some earlier works on
“learning from positive samples” [CDS20, DDS15, DGL05] also have a similar
flavor. In particular, the main result of [CDS20] is a $\mathrm{poly}(n)$ time
algorithm which, given access to samples from a Gaussian truncated by an
unknown degree-$2$ PTF, approximately recovers the truncation set; and one of
the main results of [DDS15] is an analogous $\mathrm{poly}(n)$-time algorithm
but for degree-1 PTF (i.e. LTF) truncations of the uniform distribution over
$\\{-1,1\\}^{n}$. Note that while the settings of [CDS20, DDS15] are somewhat
related to the current paper, the goals and results of those works are quite
different; in particular, the focus is on learning (as opposed to testing /
determining whether truncation has taken place), and the sample complexities
of the algorithms in [CDS20, DDS15], albeit polynomial in $n$, are polynomials
of high degree.

In terms of the specific problem we study, the work most closely related to
the current paper is that of [DNS23]. In particular, as noted earlier, in
[DNS23], the algorithm gets access to samples from either (i) $N(0,1)^{n}$ or
(ii) $N(0,1)^{n}$ conditoned on a convex set. Besides the obvious difference
in the truncation sets which are considered—convex sets in [DNS23] vis-a-vis
PTFs in the current paper—the choice of the background distribution in [DNS23]
is far more restrictive. Namely, [DNS23] requires the background distribution
to be the normal distribution $N(0,1)^{n}$, whereas the results in current
paper hold for the broad family of hypercontractive product distributions
(which includes many other distributions as well as the normal distribution).
The difference in the problem settings is also reflected in the techniques
employed in these two papers. In particular, the algorithm and analysis of
[DNS23] heavily rely on tools from convex geometry including Gaussian
isoperimetry [Bor85], the Brascamp-Lieb inequality [BL76a, BL76b], and recent
structural results for convex bodies over Gaussian space [De2021, DNS22]. In
our setting, truncation sets defined by PTFs even of degree two need not be
convex, so we must take a very different approach. The algorithm in the
current paper uses techniques originating from the study of PTFs in concrete
complexity theory, in particular on the hypercontractivity of low-degree
polynomials, anti-concentration, and the “level-$k$” inequalities [O’D14]. So
to summarize the current work vis-a-vis [DNS23], the current work studies a
different class of truncations under a significantly less restrictive
assumption on the background distribution, and our main algorithm, as well as
its analysis, are completely different from those of [DNS23].

Our lower bound argument extends and strengthens a $\tilde{\Omega}(n^{1/2})$
lower bound, given in [DNS23], for distinguishing the standard normal
distribution $N(0,1)^{n}$ from $N(0,1)^{n}|_{f^{-1}(1)}$ where $f$ is an
unknown origin-centered LTF (i.e. a degree-1 PTF); both arguments use a
variation distance lower bound between a standard multivariate normal
distribution and a multivariate normal distribution with a suitable slightly
perturbed covariance matrix. Our lower bound argument in the current paper
combines tools from the LTF lower bound mentioned above with ingredients (in
particular, the use of a “shadow sample”; see 23) from a different lower bound
from [DNS23] for symmetric slabs; extends the [DNS23] analysis from degree-1
to degree-$d$ for any constant $d$; and gives a tighter analysis than [DNS23]
which does not lose any log factors.

We end this discussion of related work with the following overarching high-
level question, which we hope will be investigated in future work: Suppose
${\cal P}$ is a background distribution and ${\cal F}$ is a class of Boolean
functions. Under what conditions can we distinguish between ${\cal D}={\cal
P}$ versus ${\cal D}={\cal P}|_{f}$ (for some $f\in\mathcal{F}$) with sample
complexity asymptotically smaller than the sample complexity of learning
$\mathcal{F}$? We view our results on distinguishing truncation by PTFs as a
step towards answering this question.

##  2 Preliminaries

We write $\mathbb{N}\mathrel{\mathop{\mathchar 58\relax}}=\\{0,1,\ldots\\}$
and $\mathbf{1}\\{\cdot\\}$ for the $0/1$ indicator function. We will write

${[n]\choose d}\mathrel{\mathop{\mathchar
58\relax}}=\\{S\subseteq[n]\mathrel{\mathop{\mathchar 58\relax}}|S|=d\\}.$

Let $(\mathbb{R},\mu)$ be a probability space. For $n\in\mathbb{N}$, we write
$L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$ for the (real) inner-product space of
functions $f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\mathbb{R}$
with the inner product

${\left\langle f,g\right\rangle}\mathrel{\mathop{\mathchar
58\relax}}=\mathop{{\bf E}\/}_{\boldsymbol{x}\sim{\mu^{\otimes
n}}}{\left[f(\boldsymbol{x})\cdot g(\boldsymbol{x})\right]}.$

Here $\mu^{\otimes n}$ denotes the product probability distribution on
$\mathbb{R}^{n}$. For $q>0$ we write

$\|f\|_{q}\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim{\mu^{\otimes
n}}}{\left[|f(\boldsymbol{x})|^{q}\right]}^{1/q}.$

In particular, for $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$, we write
$\mathrm{Vol}(f)\mathrel{\mathop{\mathchar 58\relax}}=\|f\|_{1}=\mathop{{\bf
E}\/}[f(\boldsymbol{x})]$ where $\boldsymbol{x}\sim{\mu^{\otimes n}}$.

We say that a function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ is a _degree- $d$ polynomial threshold
function (PTF)_ if there exists a polynomial $p\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\mathbb{R}$ of degree at most $d$ such that

$f(x)=\mathbf{1}\\{p(x)\geq 0\\}.$

The primary class of distributions we will consider throughout is that of
truncations of an i.i.d. product distribution $\mu^{\otimes n}$ by a
degree-$d$ PTF of at least some minimum volume; more precisely, we will
consider the following class of truncations:

$\mathcal{C}_{\mathrm{PTF}}{\left(d,\alpha\right)}\mathrel{\mathop{\mathchar
58\relax}}={\left\\{\mu^{\otimes n}\mid_{f^{-1}(1)}\
\mathrel{\mathop{\mathchar 58\relax}}f\text{ is a degree-$d$ PTF with
}\mathrm{Vol}(f)\geq\alpha\right\\}}$ (1)

where $\alpha=\alpha(n)$ may depend on $n$ (in fact we will be able to take
$\alpha$ as small as $2^{-\Theta(\sqrt{n})}$). Throughout the paper we will
assume that $d$ (the degree of the PTFs we consider) is a fixed constant
independent of the ambient dimension $n$.

###  2.1 Harmonic Analysis over Product Spaces

Our notation and terminology in this section closely follow those of O’Donnell
[O’D14]; in particular, we refer the reader to Chapter 8 of [O’D14] for
further background.

######  Definition 5.

A _Fourier basis_ for $L^{2}(\mathbb{R},\mu)$ is an orthonormal basis
$\mathcal{B}=\\{\chi_{0},\chi_{1},\ldots\\}$ with $\chi_{0}\equiv 1$.

It is well known that if $L^{2}(\mathbb{R},\mu)$ is separable,222Recall that a
metric space is _separable_ if it contains a countable dense subset. then it
has a Fourier basis (see for e.g. Section I.4 of [Con19]). Note that we can
obtain a Fourier basis for $L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$ by taking
all possible $n$-fold products of elements of $\mathcal{B}$; more formally,
for a multi-index $\alpha\in\mathbb{N}^{n}$, we define

$\chi_{\alpha}(x)\mathrel{\mathop{\mathchar
58\relax}}=\prod_{i=1}^{n}\chi_{\alpha_{i}}(x_{i}).$

Then the collection $\mathcal{B}_{n}\mathrel{\mathop{\mathchar
58\relax}}={\left\\{\chi_{\alpha}\mathrel{\mathop{\mathchar
58\relax}}\alpha_{i}\in\mathbb{N}^{n}\right\\}}$ forms a Fourier basis for
$L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$; this lets us write $f\in
L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$ as
$f=\sum_{\alpha\in\mathbb{N}^{n}}\widehat{f}(\alpha)\chi_{\alpha}$ where

$\widehat{f}(\alpha)\mathrel{\mathop{\mathchar 58\relax}}={\left\langle
f,\chi_{\alpha}\right\rangle}$

is the _Fourier coefficient of $f$ on $\alpha$_.

We can assume without loss of generality that the basis elements of
$L^{2}(\mathbb{R},\mu)$, namely ${\left\\{\chi_{0},\chi_{1},\ldots\right\\}}$,
are polynomials with $\deg(\chi_{i})=i$. This is because a polynomial basis
can be obtained for $L^{2}(\mathbb{R},\mu)$ by running the Gram-Schmidt
process. By extending this basis to $L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$ by
taking products, it follows that we may assume without loss of generality that
for a multi-index $\alpha\in\mathbb{N}^{n}$, we have
$\deg(\chi_{\alpha})=|\alpha|$ where

$|\alpha|\mathrel{\mathop{\mathchar 58\relax}}=\sum_{i=1}^{n}\alpha_{i}.$

We will also write $\\#\alpha\mathrel{\mathop{\mathchar
58\relax}}={\left|\mathrm{supp}(\alpha)\right|}$ where
$\mathrm{supp}(\alpha)\mathrel{\mathop{\mathchar
58\relax}}={\left\\{i\mathrel{\mathop{\mathchar 58\relax}}\alpha_{i}\neq
0\right\\}}$.

######  Remark 6.

While the Fourier coefficients $\\{\widehat{f}(\alpha)\\}$ depend on the
choice of basis ${\left\\{\chi_{\alpha}\right\\}}$, we will always work with
some fixed (albeit arbitrary) polynomial basis, and hence there should be no
ambiguity in referring to the coefficients as though they were unique. We
assume that the orthogonal basis $\\{\chi_{\alpha}\\}$ is “known” to the
algorithm; this is certainly a reasonable assumption for natural examples of
hypercontractive distributions (e.g. distributions with finite support, the
uniform distribution on intervals, the Gaussian distribution, etc.), and is in
line with our overall problem formulation of detecting whether a known
background distribution has been subjected to truncation.

As a consequence of orthonormality, we get that for any $f\in
L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$, we have

$\mathop{{\bf E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[f(\boldsymbol{x})\right]}=\widehat{f}(0^{n})\qquad\text{and}\qquad\|f\|_{2}^{2}=\sum_{\alpha\in\mathbb{N}^{n}}\widehat{f}(\alpha)^{2},$

with the latter called _Parseval’s formula_. We also have _Plancharel’s
formula_ , which says that

${\left\langle
f,g\right\rangle}=\sum_{\alpha\in\mathbb{N}^{n}}\widehat{f}(\alpha)\widehat{g}(\alpha).$

Finally, we write

$\mathbf{W}^{=k}[f]\mathrel{\mathop{\mathchar
58\relax}}=\sum_{|\alpha|=k}\widehat{f}(\alpha)^{2}\qquad\text{and}\qquad\mathbf{W}^{\leq
k}[f]\mathrel{\mathop{\mathchar 58\relax}}=\sum_{|\alpha|\leq
k}\widehat{f}(\alpha)^{2}$

for the _Fourier weight of $f$ at level $k$_ and the _Fourier weight of $f$ up
to level $k$_ respectively.

###  2.2 Hypercontractive Distributions

The primary analytic tools we will require in both our upper and lower bounds
are consequences of _hypercontractive_ estimates for functions in
$L^{2}(\mathbb{R}^{n},\mu^{\otimes n})$; we refer the reader to Chapters 9 and
10 of [O’D14] for further background on hypercontractivity and its
applications.

######  Definition 7.

We say that $(\mathbb{R},\mu)$ is _hypercontractive_ if for every $q\geq 2$,
there is a fixed constant $C_{q}(\mu)$ such that for every $n\geq 1$ and every
multivariate degree-$d$ polynomial $p\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\mathbb{R}$ we have

$\|p\|_{q}\leq C_{q}(\mu)^{d}\cdot\|p\|_{2}$ (2)

where $C_{q}(\mu)$ is independent of $n$ and satisfies

$C_{q}(\mu)\leq K\sqrt{q}$ (3)

for an absolute constant $K$. When the product distribution $\mu^{\otimes n}$
is clear from context, we will sometimes simply write
$C_{q}\mathrel{\mathop{\mathchar 58\relax}}=C_{q}(\mu)$ instead.

It is clear from the monotonicity of norms that $C_{q}\geq 1$; see Table 1 for
examples of hypercontractive distributions with accompanying
hypercontractivity constants $C_{q}(\mu)$.

######  Remark 8.

We note that Definition 7 is not the standard definition of a hypercontractive
product distribution (cf. Chapters 9 and 10 of [O’D14]), but is in fact an
easy consequence of hypercontractivity that is sometimes referred to as the
“Bonami lemma.” The guarantees of Equations 2 and 3 are all we require for our
purposes, and so we choose to work with this definition instead.

######  Remark 9.

While Equation 3 may seem extraneous, we note that the “level-$k$
inequalities” (Proposition 11) crucially rely on this bound on the
hypercontractivity constant $C_{q}$.

Product Distribution $\mathcal{D}$ | $C_{q}$ | Reference
---|---|---
Standard Gaussian Distribution $N(0,1)^{n}$ | $\sqrt{q-1}$ | Proposition 5.48 of [AS17]
Uniform Measure on $\\{-1,+1\\}^{n}$ | $\sqrt{q-1}$ | Theorem 9.21 of [O’D14]
Finite Product Domains $(\Omega^{n},\mu^{\otimes n})$ | $\sqrt{\frac{q}{2\min(\mu)}}$ |  [Wol07] and Fact 2.8 of [AH09]
Table 1: Examples of hypercontractive distributions, along with their
accompanying hypercontractivity constants. Here $\min(\mu)$ denotes the
minimal non-zero probability of any element in the support of the (finitely
supported) distribution $\mu$.

We turn to record several useful consequences of hypercontractivity which will
be crucial to the analysis of our estimator in Section 3 and our lower bound
in Section 4.

The following _anti-concentration_ inequality is a straightforward consequence
of hypercontractivity. A similar result for arbitrary product distributions
with finite support was obtained by Austrin–Håstad [AH09], and a similar
result for functions over $\\{-1,+1\\}^{n}$ with the uniform measure was
obtained by Dinur et al. [DFKO06]. The proof of the following proposition
closely follows that of Proposition 9.7 in [O’D14]:

######  Proposition 10 (Anti-concentration of low-degree polynomials).

Suppose $(\mathbb{R}^{n},\mu^{\otimes n})$ is a hypercontractive probability
space. Then for any degree-$d$ polynomial $p\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\mathbb{R}$ with $\mathop{{\bf E}\/}[p]=0$ and
$\mathop{{\bf Var}\/}[p]=1$, we have

$\displaystyle\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[|p(\boldsymbol{x})|\geq\frac{1}{2}\right]}\geq 0.5625\cdot c^{d}$

for a constant $c\mathrel{\mathop{\mathchar 58\relax}}=c(\mu)$ independent of
$n$.

###### Proof.

As $\mathop{{\bf E}\/}{\left[p(\boldsymbol{x})^{2}\right]}=1$, it follows by
the definition of hypercontractivity that

$\mathop{{\bf E}\/}{\left[p(\boldsymbol{x})^{4}\right]}\leq C_{4}(\mu)^{4d}.$

Applying the Paley–Zygmund inequality to the non-negative random variable
$p(\boldsymbol{x})^{2}$, we get that

$\displaystyle\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[|p(\boldsymbol{x})|\geq\frac{1}{2}\right]}$
$\displaystyle=\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})^{2}\geq\frac{1}{4}\right]}$
$\displaystyle\geq{\left(\frac{3}{4}\right)}^{2}\cdot{\left(\frac{\mathop{{\bf
E}\/}{\left[p(\boldsymbol{x})^{2}\right]}^{2}}{\mathop{{\bf
E}\/}{\left[p(\boldsymbol{x})^{4}\right]}}\right)}$ $\displaystyle\geq
0.5625\cdot{\left(\frac{1}{C_{4}(\mu)^{4}}\right)}^{d},$

completing the proof. ∎

The following proposition bounds Fourier weight up to level $k$ (i.e.
$\mathbf{W}^{\leq k}[f]$) in terms of the bias (i.e. the degree-$0$ Fourier
coefficient) of the function. We note that an analogous result for functions
over $\\{-1,+1\\}^{n}$ with the uniform measure is sometimes known as “Chang’s
Lemma” or “Talagrand’s Lemma” [Cha02, Tal96]; see also Section 9.5 of [O’D14].

######  Proposition 11 (Level-$k$ inequalities).

Suppose $(\mathbb{R},\mu)$ is hypercontractive and
$f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ is a
Boolean function. Then for all $1\leq k\leq
2\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)}$ we have

$\mathbf{W}^{\leq k}[f]\leq
K^{k}\cdot\mathrm{Vol}(f)^{2}\cdot{\left(\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)}\right)}^{k}$

where $K$ is a constant independent of $n$.

###### Proof.

Let $f^{\leq k}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{|\alpha|\leq
k}\widehat{f}(\alpha)\chi_{\alpha}$ and note that $\mathbf{W}^{\leq
k}[f]=\langle f,f^{\leq k}\rangle$. By Hölder’s inequality, we have

$\langle f,f^{\leq k}\rangle\leq\|f\cdot f^{\leq
k}\|_{1}\leq\|f\|_{s}\cdot\|f^{\leq k}\|_{t}$ (4)

for all $1\leq s,t\leq\infty$ with $1/s+1/t=1$. We will take

$t\mathrel{\mathop{\mathchar
58\relax}}=\frac{q}{k}=\frac{2}{k}\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)},$

noting that $t\geq 1$ as $k\leq q$. We next bound each term on the right hand
side of Equation 4 separately. First, note that

$\|f\|_{s}\leq\mathrm{Vol}(f)^{1/s}=\mathrm{Vol}(f)^{1-1/t}$ (5)

as $f(x)\in\\{0,1\\}$ and $s\geq 1$. Furthermore, as $t\leq q$, we have by
hypercontractivity that

$\|f^{\leq k}\|_{t}\leq\|f^{\leq k}\|_{q}\leq C_{q}^{k}\cdot\|f^{\leq
k}\|_{2}=C_{q}^{k}\cdot\sqrt{\mathbf{W}^{\leq k}[f]}$ (6)

where the first inequality is due to monotonicity of norms. Combining
Equations 4, 5 and 6 and rearranging, we get that

$\displaystyle\mathbf{W}^{\leq k}[f]$ $\displaystyle\leq
C_{q}^{2k}\cdot\mathrm{Vol}(f)^{2}\cdot{\left(\frac{1}{\mathrm{Vol}(f)}\right)}^{2/t}$
$\displaystyle\
=C_{q}^{2k}\cdot\mathrm{Vol}(f)^{2}\cdot{\left(\frac{1}{\mathrm{Vol}(f)}\right)}^{k/\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)}}$
$\displaystyle=C_{q}^{2k}\cdot\mathrm{Vol}(f)^{2}\cdot 2^{k}.$

Recall from Equation 3 (see also Remark 9) that $C_{q}^{2}\leq{K_{1}}^{2}\cdot
q=2{K_{1}}^{2}\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)}$ for an absolute
constant $K$, and so we have

$\mathbf{W}^{\leq
k}[f]\leq{K}^{k}\cdot\mathrm{Vol}(f)^{2}\cdot{\left(\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)}\right)}^{k}\qquad\text{where
}{K}=4{K_{1}}^{2},$

completing the proof. ∎

######  Remark 12.

We note that the Proposition 11 also holds for bounded functions
$f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to[-1,1]$ with
$\mathrm{Vol}(f)\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
E}\/}[|f|]$, although we will not require this.

##  3 An $O(n^{d/2})$-Sample Algorithm for Degree-$d$ PTFs

In this section, we present a $O(n^{d/2})$-sample algorithm for distinguishing
a hypercontractive product distribution $\mu^{\otimes n}$ from $\mu^{\otimes
n}$ truncated by the satisfying assignments of a degree-$d$ PTF. More
precisely, we prove the following in Section 3.2:

######  Theorem 13.

Let $\varepsilon>0$ and let $(\mathbb{R},\mu)$ be hypercontractive. There is
an algorithm, PTF-Distinguisher (Algorithm 1), with the following performance
guarantee: Given access to independent samples from any unknown distribution
${\cal D}\in\\{\mu^{\otimes
n}\\}\cup\mathcal{C}_{\mathrm{PTF}}(d,2^{-\sqrt{n}})$, the algorithm uses $T$
samples where

$T\mathrel{\mathop{\mathchar
58\relax}}=\Theta_{d}{\left(\frac{n^{d/2}}{\min{\left\\{1,\varepsilon/(1-\varepsilon),c^{\Theta(d)}/(1-\varepsilon)\right\\}}^{2}}\right)}$

with $c\mathrel{\mathop{\mathchar 58\relax}}=c(\mu)$ as in Proposition 10,
runs in $O_{d}(T\cdot n^{d})$ time, and

  1. 1.

If ${\cal D}=\mu^{\otimes n}$, then with probability at least $9/10$ the
algorithm outputs “un-truncated;”

  2. 2.

If $\mathrm{d}_{\mathrm{TV}}{\left(\mu^{\otimes
n},\mathcal{D}\right)}\geq\varepsilon$ (equivalently, ${\cal D}=\mu^{\otimes
n}|_{f}$ for some degree-$d$ PTF $f$ with
$2^{-\sqrt{n}}\leq\mathrm{Vol}(f)\leq 1-\varepsilon$), then with probability
at least $9/10$ the algorithm outputs “truncated.”

Input: $\mathcal{D}\in\\{\mu^{\otimes
n}\\}\cup\mathcal{C}_{\mathrm{PTF}}({d,2^{-\sqrt{n}}})$, $\varepsilon>0$

[0.5em] Output: “Un-truncated” or “truncated”

PTF-Distinguisher$(\mathcal{D})$:

  1. 1.

Draw $2T$ independent sample points
$\boldsymbol{x}^{(1)},\ldots,\boldsymbol{x}^{(T)},\boldsymbol{y}^{(1)},\ldots,\boldsymbol{y}^{(T)}\sim\mathcal{D}$,
where

$T\mathrel{\mathop{\mathchar
58\relax}}=\Theta_{d}{\left(\frac{n^{d/2}}{\min{\left\\{1,\varepsilon/(1-\varepsilon),c^{\Theta(d)}/(1-\varepsilon)\right\\}}^{2}}\right)}.$

  2. 2.

Compute the statistic $\mathbf{M}$ where

$\mathbf{M}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{T^{2}}{\left\langle\sum_{i=1}^{T}\widetilde{\boldsymbol{x}}^{(i)},\sum_{j=1}^{T}\widetilde{\boldsymbol{y}}^{(j)}\right\rangle}\qquad\text{with}\qquad\widetilde{\boldsymbol{x}}^{(i)}\mathrel{\mathop{\mathchar
58\relax}}={\left(\chi_{\alpha}(\boldsymbol{x}^{(i)})\right)}_{1\leq|\alpha|\leq
d}$

and $\widetilde{\boldsymbol{y}}^{(j)}$ defined similarly.

  3. 3.

Output “truncated” if
$\mathbf{M}\geq\min{\left\\{1,{\left(\frac{\varepsilon}{1-\varepsilon}\right)},\frac{c^{\Theta(d)}}{(1-\varepsilon)}\right\\}}$
and “un-truncated” otherwise.

Algorithm 1 Distinguisher for degree-$d$ PTFs. Throughout the algorithm the
constant $c\mathrel{\mathop{\mathchar 58\relax}}=c(\mu)$ is as in the proof of
Lemma 15.

Before proceeding to the proof of Theorem 13, we give a brief high-level
description of Algorithm 1. The algorithm draws $2T$ independent samples
$\\{\boldsymbol{x}^{(i)},\boldsymbol{y}^{(i)}\\}_{i\in T}$ where $T$ is as
above, and then performs a _feature expansion_ to obtain the $2T$ vectors
$\\{\widetilde{\boldsymbol{x}}^{(i)},\widetilde{\boldsymbol{y}}^{(i)}\\}_{i\in
T}$ where

$\widetilde{\boldsymbol{x}}^{(i)}\mathrel{\mathop{\mathchar
58\relax}}={\left(\chi_{\alpha}(\boldsymbol{x}^{(i)})\right)}_{1\leq|\alpha|\leq
d}$

and $\widetilde{\boldsymbol{y}}^{(i)}$ is defined similarly. The statistic
$\mathbf{M}$ employed by the algorithm to distinguish between the un-truncated
and truncated is then given by

  1. 1.

First computing the average of the kernelized
$\widetilde{\boldsymbol{x}}^{(i)}$ vectors and the kernelized
$\widetilde{\boldsymbol{y}}^{(i)}$ vectors; and then

  2. 2.

Taking the inner product between the two averaged kernel vectors.

An easy calculation, given below, relates the statistic $\mathbf{M}$ to the
low-degree (but not degree-0) Fourier weight of the truncation function (note
that if no truncation is applied then the truncation function is identically
1). The analysis then proceeds by using anti-concentration of low-degree
polynomials to show that the means of the estimators differ by
$\Omega_{\varepsilon}(1)$ between the two settings. We bound the variance of
the estimator in both the un-truncated and truncated setting (using the
level-$k$ inequalities at a crucial point in the analysis of the truncated
setting), and given a separation between the means and a bound on the
variances, it is straightforward to distinguish between the two settings using
Chebyshev’s inequality.

######  Remark 14.

We note that the trick of drawing a “bipartite” set of samples, i.e. drawing
$2T$ samples $\\{\boldsymbol{x}^{(i)},\boldsymbol{y}^{(i)}\\}_{i\in T}$, was
recently employed in the algorithm of Diakonikolas, Kane, and Pensia [DKP22]
for the problem of Gaussian mean testing. For our problem we could have
alternately used the closely related estimator $\mathbf{M}^{\prime}$ given by

$\mathbf{M}^{\prime}\mathrel{\mathop{\mathchar 58\relax}}={T\choose
2}^{-1}\sum_{i\neq
j}{\left\langle\widetilde{\boldsymbol{x}}^{(i)},\widetilde{\boldsymbol{x}}^{(j)}\right\rangle}$

to distinguish between the un-truncated and truncated distributions via a
similar but slightly more cumbersome analysis. We note that the main technical
tool used in the analysis of Diakonikolas, Kane, and Pensia [DKP22] is the
Carbery-Wright anti-concentration inequality for degree-2 polynomials in
Gaussian random variables, whereas our argument uses the above-mentioned
kernelization approach and other consequences of hypercontractivity, namely
the level-$k$ inequalities, beyond just anti-concentration.

###  3.1 Useful Preliminaries

The following lemma will be crucial in obtaining a lower-bound for the
expectation of our test statistic $\mathop{{\bf E}\/}[\mathbf{M}]$ in the
truncated setting; we note that an analogous statement in the setting of the
Boolean hypercube was obtained by Gotsman and Linial [GL94].

######  Lemma 15.

Suppose $(\mathbb{R},\mu)$ is hypercontractive. If
$f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ is a
degree-$d$ PTF, then

$\sum_{1\leq|\alpha|\leq
d}\widehat{f}(\alpha)^{2}\geq\Omega{\left(\min{\left\\{\mathrm{Vol}(f),1-\mathrm{Vol}(f),c^{\Theta(d)}\right\\}}\right)}^{2}$

for an absolute constant $c\mathrel{\mathop{\mathchar
58\relax}}=c(\mu)\in(0,1]$.

###### Proof.

We may assume that

$f(x)=\mathbf{1}\\{p(x)\geq\theta\\}$

where $p\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\mathbb{R}$ is a
degree-$d$ polynomial with $\operatorname{{\bf
E}}[p(\boldsymbol{x})]=\widehat{p}(0^{n})=0$ and
$\|p\|_{2}^{2}=\operatorname{{\bf
Var}}[p]=\sum_{\alpha}\widehat{p}(\alpha)^{2}=1$. By Cauchy–Schwarz and
Plancherel, we get

$\displaystyle{\sum_{1\leq|\alpha|\leq d}\widehat{f}(\alpha)^{2}}$
$\displaystyle={{\left(\sum_{1\leq|\alpha|\leq
d}\widehat{f}(\alpha)^{2}\right)}{\left(\sum_{1\leq|\alpha|\leq
d}\widehat{p}(\alpha)^{2}\right)}}$
$\displaystyle\geq{\left(\sum_{1\leq|\alpha|\leq
d}\widehat{f}(\alpha)\cdot\widehat{p}(\alpha)\right)}^{2}$
$\displaystyle={{\left(\mathop{{\bf E}\/}{\left[f(\boldsymbol{x})\cdot
p(\boldsymbol{x})\right]}\right)}^{2}.}$ (7)

where we made use of the the fact that $p$ is a degree-$d$ polynomial with
$\widehat{p}(0^{n})=0$ and $\operatorname{{\bf
Var}}{\left[p(\boldsymbol{x})\right]}=1$. Note that by Proposition 10, we have
that either

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})\geq\frac{1}{2}\right]}\geq\Omega{\left(c^{d}\right)}\qquad\text{or}\qquad\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})\leq-\frac{1}{2}\right]}\geq\Omega{\left(c^{d}\right)}.$
(8)

Suppose that it is the former. (As we will briefly explain later, the argument
is symmetric in the latter case.) We further break the analysis into cases
depending on the magnitude of $\theta$.

##### Case 1: $\theta\geq\frac{1}{2}$.

In this case, we have by Equation 7 that

$\displaystyle{\sum_{1\leq|\alpha|\leq d}\widehat{f}(\alpha)^{2}}$
$\displaystyle\geq{\left(\mathop{{\bf E}\/}{\left[f(\boldsymbol{x})\cdot
p(\boldsymbol{x})\right]}\right)}^{2}$ $\displaystyle={\left(\mathop{{\bf
E}\/}{\left[\mathbf{1}_{p(\boldsymbol{x})\geq\theta}\cdot
p(\boldsymbol{x})\right]}\right)}^{2}$
$\displaystyle\geq(\mathrm{Vol}(f)\cdot\theta)^{2}$
$\displaystyle\geq\Omega{\left(\mathrm{Vol}(f)^{2}\right)},$

and so the result follows.

##### Case 2: $0\leq\theta<\frac{1}{2}$.

In this case, we have by Proposition 10 that

$\mathrm{Vol}(f)=\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})\geq\theta\right]}\geq\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})\geq\frac{1}{2}\right]}\geq\Omega{\left(c^{d}\right)}.$

Once again by Equation 7, we have

${\sum_{1\leq|\alpha|\leq d}\widehat{f}(\alpha)^{2}}\geq{\left(\mathop{{\bf
E}\/}{\left[f(\boldsymbol{x})\cdot
p(\boldsymbol{x})\right]}\right)}^{2}\geq{\left({\frac{1}{2}}\operatorname{{\bf
Pr}}\left[p(\boldsymbol{x})\geq{\frac{1}{2}}\right]\right)}^{2}\geq\Omega{\left(c^{\Theta(d)}\right)},$

where the second inequality follows from $f\cdot p$ being always non-negative
and at least ${\frac{1}{2}}$ with probability $\operatorname{{\bf
Pr}}[p(\boldsymbol{x})\geq{\frac{1}{2}}].$

##### Case 3: $\theta<0$.

Consider the degree-$d$ PTF $f^{\dagger}\mathrel{\mathop{\mathchar
58\relax}}=1-f$ given by

$f^{\dagger}(x)=\mathbf{1}{\left\\{p(x)<\theta\right\\}}.$

It is easy to check that
$|\widehat{f^{\dagger}}(\alpha)|=|\widehat{f}(\alpha)|$ for all
$S\neq\emptyset$ and that $\mathrm{Vol}(f^{\dagger})=1-\mathrm{Vol}(f)$.
Repeating the above analysis then gives that

$\sum_{1\leq|\alpha|\leq d}\widehat{f}(\alpha)^{2}=\sum_{1\leq|\alpha|\leq
d}\widehat{f^{\dagger}}(\alpha)^{2}\geq\Omega{\left(\mathrm{Vol}(f^{\dagger})^{2}\cdot
c^{\Theta(d)}\right)}=\Omega{\left({\left(1-\mathrm{Vol}(f)\right)}^{2}\cdot
c^{\Theta(d)}\right)}.$

Putting Cases 1 through 3 together, we get that

$\sum_{1\leq|\alpha|\leq
d}\widehat{f}(\alpha)^{2}\geq\Omega{\left(\min{\left\\{\mathrm{Vol}(f),1-\mathrm{Vol}(f),c^{\Theta(d)}\right\\}}\right)}^{2},$
(9)

completing the proof. Recall, however, that we assumed that

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})\geq\frac{1}{2}\right]}\geq\Omega{\left(c^{d}\right)}$

in Equation 8. Suppose that we instead have

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[p(\boldsymbol{x})\leq-\frac{1}{2}\right]}\geq\Omega{\left(c^{d}\right)}.$

Then note that the same trick used in Case 3 by considering $f^{\dagger}$
instead of $f$ and repeating the three cases completes the proof. ∎

We will also require the following two lemmas which are closely linked to the
_linearization problem for orthogonal polynomials_ (see Section 6.8 of
[AAR99]). The first lemma bounds the magnitude of the Fourier coefficients of
the _product_ of basis functions; while the estimate below relies on
hypercontractivity, we note that exact expressions for the Fourier
coefficients are known for various classes of orthogonal polynomials including
the Chebyshev, Hermite, and Laguerre polynomials.

######  Lemma 16.

Suppose $(\mathbb{R},\mu)$ is hypercontractive. Let
$\alpha,\beta,\gamma\in\mathbb{N}^{n}$. Then

${\left\langle\chi_{\alpha},\chi_{\beta}\cdot\chi_{\gamma}\right\rangle}\leq
C_{4}({\mu})^{|\beta|+|\gamma|}.$

###### Proof.

Using Cauchy–Schwarz, we have that

$\displaystyle{\left\langle\chi_{\alpha},\chi_{\beta}\cdot\chi_{\gamma}\right\rangle}$
$\displaystyle=\mathop{{\bf E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[\chi_{\alpha}(\boldsymbol{x})\cdot{\left(\chi_{\beta}(\boldsymbol{x})\cdot\chi_{\gamma}(\boldsymbol{x})\right)}\right]}$
$\displaystyle\leq\sqrt{\mathop{{\bf E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[\chi_{\alpha}(\boldsymbol{x})^{2}\right]}\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[\chi_{\beta}(\boldsymbol{x})^{2}\cdot\chi_{\gamma}(\boldsymbol{x})^{2}\right]}}$
$\displaystyle=\sqrt{\mathop{{\bf E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[\chi_{\beta}(\boldsymbol{x})^{2}\cdot\chi_{\gamma}(\boldsymbol{x})^{2}\right]}}$
due to the orthonormality of $\chi_{\alpha}$. Using Cauchy–Schwarz once again,
we have that
$\displaystyle{\left\langle\chi_{\alpha},\chi_{\beta}\cdot\chi_{\gamma}\right\rangle}$
$\displaystyle\leq{\left(\mathop{{\bf E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[\chi_{\beta}(\boldsymbol{x})^{4}\right]}\cdot\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mu^{\otimes
n}}{\left[\chi_{\gamma}(\boldsymbol{x})^{4}\right]}\right)}^{1/4}$
$\displaystyle=\|\chi_{\beta}\|_{4}\cdot\|\chi_{\gamma}\|_{4}$
$\displaystyle\leq C_{4}(\mu)^{|\beta|+|\gamma|}$

where the final inequality uses hypercontractivity and the fact that
$\chi_{\beta}$ ($\chi_{\gamma}$ respectively) is a polynomial of two-norm 1
and degree at most $|\beta|$ (at most $|\gamma|$ respectively). ∎

Finally, we also require the following combinatorial lemma.

######  Lemma 17.

Given $d\in\mathbb{N}$ and a fixed multi-index $\alpha\in\mathbb{N}^{n}$ with
$|\alpha|\mathrel{\mathop{\mathchar 58\relax}}=k\leq 2d$, we have

$\\#{\left\\{(\beta,\gamma)\in\mathbb{N}^{n}\times\mathbb{N}^{n}\mathrel{\mathop{\mathchar
58\relax}}|\beta|,|\gamma|\leq d\text{ and
}{\left\langle\chi_{\alpha},\chi_{\beta}\chi_{\gamma}\right\rangle}\neq
0\right\\}}\leq O_{d}{\left(n^{d-{\left\lceil k/2\right\rceil}}\right)}.$

###### Proof.

We will upper bound the number of pairs $(\beta,\gamma)$ such that
$|\beta|,|\gamma|\leq d$ and
${\left\langle\chi_{\alpha},\chi_{\beta}\chi_{\gamma}\right\rangle}\neq 0$; so
fix such a pair $(\beta,\gamma)$.

We first note that for any $i\notin\mathrm{supp}(\alpha)$, we must have
$\beta_{i}=\gamma_{i}$; for otherwise
${\left\langle\chi_{\alpha},\chi_{\beta}\chi_{\gamma}\right\rangle}=0$ due to
orthonormality of $\chi_{\beta_{i}}$ and $\chi_{\gamma_{i}}$. Also, for each
$i\in\mathrm{supp}(\alpha)$, we must have
$\beta_{i}+\gamma_{i}\geq\alpha_{i}$, since if
$\beta_{i}+\gamma_{i}<\alpha_{i}$, then

${\left\langle\chi_{\beta_{i}}\cdot\chi_{\gamma_{i}},\chi_{\alpha_{i}}\right\rangle}=0$

by orthonormality and the fact that $\chi_{\beta_{i}}\cdot\chi_{\gamma_{i}}$
is a linear combination of basis functions $\\{\chi_{j}\\}_{j<\alpha_{i}}.$

Summing over all $i\in\mathrm{supp}(\alpha)$, we get that

$\sum_{i\in\mathrm{supp}(\alpha)}\beta_{i}+\gamma_{i}\geq\sum_{i\in\mathrm{supp}(\alpha)}\alpha_{i}=|\alpha|,$

and so it follows that either

$\sum_{i\in\mathrm{supp}(\alpha)}\beta_{i}\geq{\left\lceil
k/2\right\rceil}\qquad\text{or}\qquad\sum_{i\in\mathrm{supp}(\alpha)}\gamma_{i}\geq{\left\lceil
k/2\right\rceil};$

without loss of generality we suppose it is the former. It follows that the
total number of ways of choosing such a pair $(\beta,\gamma)$ is bounded by

$\displaystyle O_{d}(1)\cdot O_{d}(1)\cdot\sum_{j=0}^{d-\lceil
k/2\rceil}(n-|\mathrm{supp}(\alpha)|)^{j}\leq
O_{d}(1)\cdot\sum_{j=0}^{d-\lceil k/2\rceil}n^{j}\leq O_{d}(n^{d-{\left\lceil
k/2\right\rceil}})$

where

  * •

The first two $O_{d}(1)$ factors bound the number of possible outcomes of
$(\beta_{i})_{i\in\mathrm{supp}(\alpha)}$ (recall that each
$\beta_{i}\in[0,d]$ and $|\mathrm{supp}(\alpha)|\leq 2d$) and
$(\gamma)_{i\in\mathrm{supp}(\alpha)}$ respectively); and

  * •

The third term on the LHS upper bounds the number of choices for
${\left(\beta_{i}\right)}_{i\notin\mathrm{supp}(\alpha)}$. Recall that for
$i\notin\mathrm{supp}(\alpha)$ we must have $\beta_{i}=\gamma_{i}$, and so

${\left(\beta_{i}\right)}_{i\notin\mathrm{supp}(\alpha)}={\left(\gamma_{i}\right)}_{i\notin\mathrm{supp}(\alpha)}$

so we need only bound the number of choices of
${\left(\beta_{i}\right)}_{i\notin\mathrm{supp}(\alpha)}$; moreover, as

$\sum_{i}\beta_{i}\leq d\quad\text{and
}\sum_{i\in\mathrm{supp}(\alpha)}\beta_{i}\geq{\left\lceil
k/2\right\rceil},\text{ we must
have}\sum_{i\notin\mathrm{supp}(\alpha)}\beta_{i}\leq d-{\left\lceil
k/2\right\rceil},$

completing the proof. ∎

###  3.2 Proof of Theorem 13

  * _Proof of Theorem 13._

Throughout, we will write

$m\mathrel{\mathop{\mathchar
58\relax}}=\\#{\left\\{\alpha\in\mathbb{N}^{n}\mathrel{\mathop{\mathchar
58\relax}}1\leq|\alpha|\leq d\right\\}}.$

Recalling that there are at most ${{n+k-1}\choose k}$ multi-indices
$\alpha\in\mathbb{N}^{n}$ with $|\alpha|=k$, we have that

$m\leq O_{d}(n^{d}).$

We compute the mean and variance of the estimator $\mathbf{M}$ in each case
(i.e. when $\mathcal{D}=\mu^{\otimes n}$ and when
$\mathcal{D}\in\mathcal{C}_{\mathrm{PTF}}(d,2^{-\sqrt{n}})$) separately.

##### Case 1: $\mathcal{D}=\mu^{\otimes n}$.

For brevity (and to distinguish the calculations in this case from the
following one), we denote the un-truncated distribution by

$\mathcal{D}_{u}\mathrel{\mathop{\mathchar 58\relax}}=\mu^{\otimes n}.$

When
$\boldsymbol{x}^{(1)},\ldots,\boldsymbol{x}^{(T)},\boldsymbol{y}^{(1)},\ldots,\boldsymbol{y}^{(T)}\sim\mathcal{D}_{u}$,
we have by bi-linearity of the inner product that

$\displaystyle\mathop{{\bf E}\/}_{\mathcal{D}_{u}}{\left[\mathbf{M}\right]}$
$\displaystyle=\frac{1}{T^{2}}\sum_{i,j=1}^{T}\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[{\left\langle\widetilde{\boldsymbol{x}}^{(i)},\widetilde{\boldsymbol{y}}^{(j)}\right\rangle}\right]}$
$\displaystyle=\sum_{1\leq|\alpha|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[\chi_{\alpha}(\boldsymbol{x})\cdot\chi_{\alpha}(\boldsymbol{y})\right]}$
$\displaystyle=\sum_{1\leq|\alpha|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[\chi_{\alpha}(\boldsymbol{x})\right]}\cdot\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[\chi_{\alpha}(\boldsymbol{y})\right]}$
$\displaystyle=0$ (10)

as $\boldsymbol{x},\boldsymbol{y}\sim\mathcal{D}_{u}$ are independent samples
and also because of the orthonormality of $\\{\chi_{\alpha}\\}$.

Turning to the variance, we have

$\displaystyle\mathop{{\bf
Var}\/}_{\mathcal{D}_{u}}[\mathbf{M}]=\frac{1}{T^{4}}{\left(\sum_{i,j=1}^{T}\mathop{{\bf
Var}\/}_{\mathcal{D}_{u}}{\left[{\left\langle\widetilde{\boldsymbol{x}}^{(i)},\widetilde{\boldsymbol{y}}^{(j)}\right\rangle}\right]}\right)}=\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}^{2}\right]}-\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}\right]}^{2}\right)}$
(11)

where $\boldsymbol{x},\boldsymbol{y}\sim\mathcal{D}$ are independent samples.
In this case, we have by our previous calculation (Equation 10) that this is
in fact equal to

$\displaystyle\mathop{{\bf Var}\/}_{\mathcal{D}_{u}}[\mathbf{M}]$
$\displaystyle=\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}{\left\langle\widetilde{\boldsymbol{y}},\widetilde{\boldsymbol{x}}\right\rangle}\right]}\right)}$
$\displaystyle=\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{{\boldsymbol{x}}\sim\mathcal{D}_{u}}{\left[{\widetilde{\boldsymbol{x}}}^{\mathsf{T}}\mathop{{\bf
E}\/}_{{\boldsymbol{y}}\sim\mathcal{D}_{u}}{\left[\widetilde{\boldsymbol{y}}\cdot\widetilde{\boldsymbol{y}}^{\mathsf{T}}\right]}\widetilde{\boldsymbol{x}}\right]}\right)}$
$\displaystyle=\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[\sum_{1\leq|\alpha|\leq
d}\chi_{\alpha}(\boldsymbol{x})^{2}\right]}\right)}$
$\displaystyle=\frac{m}{T^{2}}$ $\displaystyle\leq
O_{d}{\left(\frac{n^{d}}{T^{2}}\right)}$ (12)

where we used orthonormality as well as the fact that $\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[\widetilde{\boldsymbol{y}}\cdot\widetilde{\boldsymbol{y}}^{\mathsf{T}}\right]}=\mathrm{Id}_{m}.$

##### Case 2: $\mathrm{d}_{\mathrm{TV}}{\left(\mu^{\otimes
n},\mathcal{D}\right)}\geq\varepsilon$ with
$\mathcal{D}\in\mathcal{C}_{\mathrm{PTF}}(d,2^{-\sqrt{n}})$.

For brevity, we denote the truncated distribution by

$\mathcal{D}_{t}\mathrel{\mathop{\mathchar 58\relax}}=\mu^{\otimes
n}|_{f^{-1}(1)}.$

In this case, $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ is a degree-$d$ PTF with

$\mathrm{Vol}(f)\in{\left[2^{-\sqrt{n}},1-\varepsilon\right]}.$

We may assume that

$f(x)=\mathbf{1}\\{p(x)\geq\theta\\}$

where $p\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\mathbb{R}$ is a
degree-$d$ polynomial with $\widehat{p}(0^{n})=0$ and
$\|p\|_{2}^{2}=\operatorname{{\bf
Var}}[p]=\sum_{\alpha}\widehat{p}(\alpha)^{2}=1$.

We have the following easy relation between the Fourier coefficients of $f$
and the means of the characters $\\{\chi_{\alpha}\\}$ under the truncated
distribution $\mathcal{D}_{t}$:

$\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathcal{D}_{t}}{\left[\chi_{\alpha}(\boldsymbol{x})\right]}=\frac{1}{\mathrm{Vol}(f)}\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathcal{D}_{u}}{\left[f(\boldsymbol{x})\chi_{\alpha}(\boldsymbol{x})\right]}=\frac{\widehat{f}(\alpha)}{\mathrm{Vol}(f)}.$
(13)

We thus have

$\displaystyle\mathop{{\bf E}\/}_{\mathcal{D}_{t}}{\left[\mathbf{M}\right]}$
$\displaystyle=\sum_{1\leq|\alpha|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\chi_{\alpha}(\boldsymbol{x})\right]}\cdot\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\chi_{\alpha}(\boldsymbol{y})\right]}$
$\displaystyle=\frac{1}{\mathrm{Vol}(f)^{2}}\sum_{1\leq|\alpha|\leq
d}\widehat{f}(\alpha)^{2}$
$\displaystyle\geq\frac{1}{\mathrm{Vol}(f)^{2}}\cdot\Omega{\left(\min{\left\\{\mathrm{Vol}(f),1-\mathrm{Vol}(f),c^{\Theta(d)}\right\\}}\right)}^{2}$
$\displaystyle\geq\Omega{\left(\min{\left\\{1,{\left(\frac{1-\mathrm{Vol}(f)}{\mathrm{Vol}(f)}\right)},\frac{c^{\Theta(d)}}{\mathrm{Vol}(f)}\right\\}}\right)}^{2}$
(14)

where the second line follows from Equation 13 and the final inequality is due
to Lemma 15; here $c\mathrel{\mathop{\mathchar 58\relax}}=c(\mu)$ is as in
Proposition 10.

Turning to the variance of the estimator, we have as before by Equation 11
that

$\displaystyle\mathop{{\bf
Var}\/}_{\mathcal{D}_{t}}[\mathbf{M}]=\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}^{2}\right]}-\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}\right]}^{2}\right)}$
$\displaystyle\leq\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}{\left\langle\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}}\right\rangle}\right]}\right)}$
$\displaystyle=\frac{1}{T^{2}}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[{\left(\sum_{1\leq|\alpha|\leq
d}\chi_{\alpha}{\left(\boldsymbol{x}\right)}\chi_{\alpha}{\left(\boldsymbol{y}\right)}\right)}^{2}\right]}\right)}$
$\displaystyle=\frac{1}{T^{2}}\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\sum_{1\leq|\beta|,|\gamma|\leq
d}\chi_{\beta}(\boldsymbol{x})\chi_{\gamma}{\left(\boldsymbol{x}\right)}\chi_{\beta}(\boldsymbol{y})\chi_{\gamma}{\left(\boldsymbol{y}\right)}\right]}$
$\displaystyle=\frac{1}{T^{2}}\sum_{1\leq|\beta|,|\gamma|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\chi_{\beta}\chi_{\gamma}\right]}^{2}.$

Similar to Equation 13 we can write

$\displaystyle\sum_{1\leq|\beta|,|\gamma|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\chi_{\beta}\chi_{\gamma}\right]}^{2}$
$\displaystyle=\sum_{1\leq|\beta|,|\gamma|\leq
d}{\left(\frac{1}{\mathrm{Vol}(f)}\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[f\cdot\chi_{\beta}\chi_{\gamma}\right]}\right)}^{2}$
$\displaystyle=\frac{1}{\mathrm{Vol}(f)^{2}}\sum_{{1\leq}|\beta|,|\gamma|\leq
d}{\left(\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}{\left[f\cdot{\left(\sum_{|\alpha|\leq
2d}{\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\chi_{\alpha}\right)}\right]}\right)}^{2}$
$\displaystyle=\frac{1}{\mathrm{Vol}(f)^{2}}\sum_{1\leq|\beta|,|\gamma|\leq
d}{\left(\sum_{|\alpha|\leq
2d}{\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\widehat{f}(\alpha)\right)}^{2}$
$\displaystyle\leq\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{1\leq|\beta|,|\gamma|\leq
d}{\left(\sum_{|\alpha|\leq
2d}{|}\widehat{f}(\alpha){|}\cdot\mathbf{1}{\left({\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\neq
0\right)}\right)}^{2}$ (15)

where the $O_{d}(1)$ factor in Equation 15 comes from the RHS of Lemma 16.
Now, observe that for a fixed $(\beta,\gamma)$ pair with
$1\leq|\beta|,|\gamma|\leq d$ there are $O_{d}(1)$ many multi-indices $\alpha$
such that
${\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\neq 0$ as
we must have
$\mathrm{supp}(\alpha)\subseteq\mathrm{supp}(\beta)\cup\mathrm{supp}(\gamma)$.
Combining this observation with the Cauchy-Schwarz inequality

${\left(\sum_{i=1}^{t}a_{i}\right)}^{2}\leq
t\cdot{\left(\sum_{i=1}^{t}a_{i}^{2}\right)},$

we have

$\displaystyle\sum_{1\leq|\beta|,|\gamma|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\chi_{\beta}\chi_{\gamma}\right]}^{2}$
$\displaystyle\leq\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{1\leq|\beta|,|\gamma|\leq
d}\sum_{|\alpha|\leq
2d}\widehat{f}(\alpha)^{2}\cdot\mathbf{1}{\left({\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\neq
0\right)}$
$\displaystyle=\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{|\alpha|\leq
2d}\sum_{1\leq|\beta|,|\gamma|\leq
d}\widehat{f}(\alpha)^{2}\cdot\mathbf{1}{\left({\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\neq
0\right)}$
$\displaystyle=\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{k=0}^{2d}\sum_{|\alpha|=k}\sum_{1\leq|\beta|,|\gamma|\leq
d}\widehat{f}(\alpha)^{2}\cdot\mathbf{1}{\left({\left\langle\chi_{\beta}\chi_{\gamma},\chi_{\alpha}\right\rangle}\neq
0\right)}$
$\displaystyle\leq\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{k=0}^{2d}\sum_{|\alpha|=k}\widehat{f}(\alpha)^{2}\cdot
O_{d}{\left(n^{d-{\left\lceil k/2\right\rceil}}\right)}$

where the final inequality is due to Lemma 17. Finally, we have that

$\displaystyle\sum_{1\leq|\beta|,|\gamma|\leq d}\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}{\left[\chi_{\beta}\chi_{\gamma}\right]}^{2}$
$\displaystyle\leq\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{k=0}^{2d}O_{d}{\left(n^{d-{\left\lceil
k/2\right\rceil}}\right)}\cdot\mathbf{W}^{=k}[f]$
$\displaystyle\leq\frac{O_{d}(1)}{\mathrm{Vol}(f)^{2}}\sum_{k=0}^{2d}O_{d}{\left(n^{d-{\left\lceil
k/2\right\rceil}}\right)}\cdot{\left(\mathrm{Vol}(f)^{2}\cdot{\left(\log{\left(\frac{1}{\mathrm{Vol}(f)}\right)}\right)}^{k}\right)}$
(16) $\displaystyle\leq
O_{d}(1){\left(\sum_{k=0}^{2d}O_{d}{\left(n^{d-{\left\lceil
k/2\right\rceil}}\right)}\cdot n^{k/2}\right)}$ $\displaystyle\leq
O_{d}(1)\cdot n^{d},$ (17)

where Equation 16 is by the level-$k$ inequalities (Proposition 11) and
Equation 17 uses the fact that $\mathrm{Vol}(f)\geq 2^{-\sqrt{n}}$ (which is
by assumption). Putting everything together, we get that

$\mathop{{\bf Var}\/}_{\mathcal{D}_{t}}[\mathbf{M}]\leq
O_{d}{\left(\frac{n^{d}}{T^{2}}\right)}.$ (18)

To summarize, when $\mathcal{D}=\mu^{\otimes n}$, we have from Equations 10
and 12 that

$\mathop{{\bf
E}\/}_{\mathcal{D}_{u}}[\mathbf{M}]=0\qquad\text{and}\qquad\mathop{{\bf
Var}\/}_{\mathcal{D}_{u}}[\mathbf{M}]=O_{d}{\left(\frac{n^{d}}{T^{2}}\right)}.$
(19)

On the other hand, when
$\mathcal{D}\in\mathcal{C}_{\mathrm{PTF}}(d,2^{-\sqrt{n}})$ with
$\mathrm{d}_{\mathrm{TV}}(\mathcal{D},\mu^{\otimes n})\geq\varepsilon$ , we
have from Equations 14 and 18 that

$\mathop{{\bf
E}\/}_{\mathcal{D}_{t}}[\mathbf{M}]\geq\Omega{\left(\min{\left\\{1,{\left(\frac{\varepsilon}{1-\varepsilon}\right)},{\left(\frac{c^{\Theta(d)}}{1-\varepsilon}\right)}\right\\}}\right)}^{2}\qquad\text{and}\qquad\mathop{{\bf
Var}\/}_{\mathcal{D}_{t}}[\mathbf{M}]\leq
O_{d}{\left(\frac{n^{d}}{T^{2}}\right)}.$ (20)

For the number of samples being

$T=\Theta_{d}{\left(\frac{n^{d/2}}{\min{\left\\{1,\varepsilon/(1-\varepsilon),c^{\Theta(d)}/(1-\varepsilon)\right\\}}^{2}}\right)},$

the correctness of the distinguishing algorithm Algorithm 1 follows directly
from Equation 19 and Equation 20 by a simple application of Chebyshev’s
inequality. ∎

##  4 An $\Omega(n^{d/2})$-Sample Lower Bound for Distinguishing PTFs

In this section, we show that there exists a hypercontractive product
distribution for which distinguishing truncation by a degree-$d$ PTF requires
$\Omega(n^{d/2})$ samples. In fact, we prove this for arguably the simplest
hypercontractive product measure, namely the uniform distribution on the
Boolean hypercube $\\{-1,+1\\}^{n}$. As discussed in the introduction, this
strengthens the $\Omega(n^{d/4})$-sample lower bound for distinguishing low-
volume PTFs (cf. Appendix A) and matches our upper bound from Theorem 13 up to
an absolute constant factor (depending only on the degree-$d$).

######  Notation 18.

Throughout this section, we will write $\mathcal{D}_{u}$ to denote the uniform
distribution over $\\{-1,+1\\}^{n}$.

######  Theorem 19.

Let $A$ be any algorithm which is given access to samples from some unknown
distribution $\mathcal{D}$ over $\mathbb{R}^{n}$ and has the following
performance guarantee:

  1. 1.

If $\mathcal{D}=\mathcal{D}_{u}$, then with probability at least $99/100$ the
algorithm $A$ outputs “un-truncated”; and

  2. 2.

If $\mathcal{D}=\mathcal{D}_{u}|_{f^{-1}(1)}$ where
$f\mathrel{\mathop{\mathchar 58\relax}}\\{-1,+1\\}^{n}\to\\{0,1\\}$ is a
degree-$d$ PTF with $\mathrm{Vol}(f)\in{\left[1/2\pm o_{n}(1)\right]}$, then
with probability at least $99/100$ the algorithm $A$ outputs “truncated”.

Then $A$ must use at least $\Omega(n^{d/2})$ samples from $\mathcal{D}$.

After setting up preliminary results in Section 4.1, we will prove Theorem 19
via establishing a total variation distance bound over an appropriate pair of
distributions in Section 4.2.

###  4.1 Useful Preliminaries

We first recall a recent upper bound on the total variation distance between
$n$-dimensional Gaussians due to Devroye, Mehrabian and Reddad [DMR20].

######  Theorem 20 (Theorem 1.1 of [DMR20]).

Let $\Sigma_{1},\Sigma_{2}$ be two $m\times m$ positive definite covariance
matrices and let $\lambda_{1},\dots,\lambda_{m}$ be the eigenvalues of
$\Sigma_{1}^{-1}\Sigma_{2}-I_{m}$. Then

$\mathrm{d}_{\mathrm{TV}}{\left(N(0^{m},\Sigma_{1}),N(0^{m},\Sigma_{2})\right)}\leq{\frac{3}{2}}\cdot\min\left\\{1,\sqrt{\lambda_{1}^{2}+\cdots+\lambda_{m}^{2}}\right\\}$

1. Draw the vector ${\left(\widehat{\boldsymbol{p}}(S)\right)}_{S\in{[n]\choose d}}=\mathrel{\mathop{\mathchar 58\relax}}\widehat{\boldsymbol{p}}\sim N(0,1)^{{n\choose d}}$. 2. Set $\boldsymbol{p}(x)\mathrel{\mathop{\mathchar 58\relax}}=\sum_{{\begin{subarray}{c}S\subseteq[n]\\\ |S|=d\end{subarray}}}\widehat{\boldsymbol{p}}(S)x_{S}\qquad\text{where}\qquad x_{S}\mathrel{\mathop{\mathchar 58\relax}}=\prod_{i\in S}x_{i},$ and output the degree-$d$ PTF $\boldsymbol{f}(x)\mathrel{\mathop{\mathchar 58\relax}}=\mathbf{1}{\left\\{\boldsymbol{p}(x)\geq 0\right\\}}$.

Figure 1: A draw of $\boldsymbol{f}$ from the distribution $\mathcal{F}_{d}$

Next, we introduce a distribution $\mathcal{F}_{d}$ (cf. Figure 1) over
multilinear degree-$d$ PTFs over the Boolean hypercube. The following lemma
shows that a random PTF $\boldsymbol{f}$ drawn from $\mathcal{F}_{d}$ is close
to being balanced with high probability.

######  Lemma 21.

For $\boldsymbol{f}\sim\mathcal{F}_{d}$ as described in Figure 1, we have with
probability at least $1-o(1)$ that

$\mathrm{Vol}(\boldsymbol{f})\in\left[\frac{1}{2}-o(1),\frac{1}{2}+o(1)\right].$

The proof of Lemma 21 will make use of the following well-known fact
characterizing the probability that two vectors are both satisfying
assignments of a random origin-centered LTF that has Gaussian coordinates. The
fact follows immediately from spherical symmetry of the standard Gaussian
distribution, and is sometimes known as “Sheppard’s formula” (see Section 11.1
of [O’D14]).

######  Fact 22.

Let $u,v$ be unit vectors in $\mathbb{R}^{m}$. We have

$\mathop{{\bf Pr}\/}_{\boldsymbol{g}\sim N(0,I_{m})}[\boldsymbol{g}\cdot u\geq
0\text{~{}and~{}}\boldsymbol{g}\cdot v\geq
0]={\frac{1}{2}}-{\frac{\arccos(u\cdot v)}{2\pi}}.$

We now turn to the proof of Lemma 21.

  * _Proof of Lemma 21._

If $d$ is odd then $\boldsymbol{p}(-x)=-\boldsymbol{p}(x)$ (i.e.
$\boldsymbol{p}$ is an odd function); since for any fixed $x$ we have that
$\boldsymbol{p}(x)=0$ with probability 0, it follows that
$\mathrm{Vol}(\boldsymbol{f})=1/2$ with probability $1$ for odd $d$. So in the
rest of the argument we may suppose $d$ is even (though the argument we give
will work for all $d\geq 1$, even or odd).

We first observe that $\operatorname{{\bf
E}}[\mathrm{Vol}(\boldsymbol{f})]=1/2$: this is because

$\displaystyle\operatorname{{\bf E}}[\mathrm{Vol}(\boldsymbol{f})]$
$\displaystyle=\mathop{{\bf E}\/}_{\boldsymbol{p}}\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\\{-1,+1\\}^{n}}[\boldsymbol{p}(\boldsymbol{x})\geq
0]\right]=\mathop{{\bf E}\/}_{\boldsymbol{x}}\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{p}}\left[\boldsymbol{p}(\boldsymbol{x})\geq
0\right]\right]=1/2,$

where the last equality is because for each $x\in(\mathbb{R}^{n}\setminus
0^{n})$ we have $\mathop{{\bf Pr}\/}_{\boldsymbol{p}}[\boldsymbol{p}(x)\geq
0]=1/2.$

Next, we upper bound the variance of $\mathrm{Vol}(\boldsymbol{f})$. We have

$\operatorname{{\bf Var}}[\mathrm{Vol}(\boldsymbol{f})]=\mathop{{\bf
E}\/}[\mathrm{Vol}(\boldsymbol{f})^{2}]-\mathop{{\bf
E}\/}[\mathrm{Vol}(\boldsymbol{f})]^{2}=\mathop{{\bf
E}\/}[\mathrm{Vol}(\boldsymbol{f})^{2}]-{\frac{1}{4}},$

so our goal is to show that $\mathop{{\bf
E}\/}[\mathrm{Vol}(\boldsymbol{f})^{2}]$ is $1/4+o(1)$.

$\displaystyle\mathop{{\bf E}\/}[\mathrm{Vol}(\boldsymbol{f})^{2}]$
$\displaystyle=\mathop{{\bf E}\/}_{\boldsymbol{p}}\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\\{-1,+1\\}^{n}}[\boldsymbol{p}(\boldsymbol{x})\geq
0]^{2}\right]$ $\displaystyle=\mathop{{\bf
E}\/}_{\boldsymbol{p}}\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}[\boldsymbol{p}(\boldsymbol{x})\geq
0\text{~{}and~{}}\boldsymbol{p}(\boldsymbol{y})\geq 0]\right]$
$\displaystyle=\mathop{{\bf
E}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{p}}[\boldsymbol{p}(\boldsymbol{x})\geq
0\text{~{}and~{}}\boldsymbol{p}(\boldsymbol{y})\geq 0]\right]$
$\displaystyle=\mathop{{\bf
E}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{p}}\left[\sum_{S\in{[n]\choose
d}}\widehat{\boldsymbol{p}}(S)\boldsymbol{x}_{S}\geq
0\text{~{}and~{}}\sum_{S\in{[n]\choose
d}}\widehat{\boldsymbol{p}}(S)\boldsymbol{y}_{S}\geq 0\right]\right]$
$\displaystyle=\mathop{{\bf
E}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}\left[\mathop{{\bf
Pr}\/}_{\widehat{\boldsymbol{p}}\sim N(0,1)^{[n]\choose
d}}\left[\widehat{\boldsymbol{p}}\cdot\Phi(\boldsymbol{x})\geq
0\text{~{}and~{}}\widehat{\boldsymbol{p}}\cdot\Phi(\boldsymbol{y})\geq
0\right]\right]$ (21)

where we define $\Phi\mathrel{\mathop{\mathchar
58\relax}}\\{-1,+1\\}^{n}\to\\{-1,+1\\}^{n\choose d}$ as

$\Phi(x)={\left(x_{S}\right)}_{S\in{[n]\choose d}}.$

We write $\Phi^{\prime}(x)$ to denote ${\Phi(x)}/{\sqrt{{n\choose d}}}$, so
$\Phi^{\prime}(x)$ is $\Phi(x)$ normalized to be a unit vector in
$\mathbb{R}^{{n\choose d}}.$ By 22 we have that

$\displaystyle(\ref{eq:rutabaga})$ $\displaystyle=\mathop{{\bf
E}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}\left[{\frac{1}{2}}-{\frac{\arccos(\Phi^{\prime}(x)\cdot\Phi^{\prime}(y))}{2\pi}}\right].$
(22)

Let

$h(x,y)\mathrel{\mathop{\mathchar
58\relax}}=\Phi^{\prime}(x)\cdot\Phi^{\prime}(y)={\frac{\sum_{S\in{[n]\choose
d}}x_{S}y_{S}}{{n\choose d}}}.$

We see that $h(x,y)$ is a degree-$2d$ homogeneous polynomial with ${n\choose
d}$ Fourier coefficients each of which is ${n\choose d}^{-1}$, so
$\operatorname{{\bf
E}}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}[h(\boldsymbol{x},\boldsymbol{y})]=0$
and $\operatorname{{\bf Var}}[h]=\|h\|_{2}^{2}={n\choose d}\cdot{n\choose
d}^{-2}={n\choose d}^{-1}$. It follows from Chebyshev’s inequality that

$\operatorname{{\bf Pr}}\left[h(x,y)>t/{n\choose d}^{1/2}\right]\leq 1/t^{2},$

so in particular we have that $\operatorname{{\bf
Pr}}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}[\Phi^{\prime}(\boldsymbol{x})\cdot\Phi^{\prime}(\boldsymbol{y})>{n\choose
d}^{-1/3}]\leq{n\choose d}^{-1/3}.$ Since
${\frac{1}{2}}-{\frac{\arccos(\Phi^{\prime}(x)\cdot\Phi^{\prime}(y))}{2\pi}}$
is always at most $1/2$, we get that

$\displaystyle(\ref{eq:blue-pumpkin})$
$\displaystyle\leq\left({\frac{1}{2}}-{\frac{\arccos({n\choose
d}^{-1/3})}{2\pi}}\right)+{\frac{1}{2}}\cdot\mathop{{\bf
Pr}\/}_{\boldsymbol{x},\boldsymbol{y}\sim\\{-1,+1\\}^{n}}\left[\Phi^{\prime}(\boldsymbol{x})\cdot\Phi^{\prime}(\boldsymbol{y})>{n\choose
d}^{-1/3}\right]$
$\displaystyle\leq\left({\frac{1}{2}}-{\frac{\arccos({n\choose
d}^{-1/3})}{2\pi}}\right)+{\frac{1}{2}}\cdot{n\choose d}^{-1/3}$
$\displaystyle\leq{\frac{1}{2}}-{\frac{\pi/2-2{n\choose
d}^{-1/3}}{2\pi}}+{\frac{1}{2}}\cdot{n\choose d}^{-1/3}$
$\displaystyle\leq{\frac{1}{4}}+C{n\choose d}^{-1/3}$

for an absolute constant $C>0$. So $\operatorname{{\bf
Var}}[\mathrm{Vol}(\boldsymbol{f})]\leq C{n\choose d}^{-1/3}$, and hence
Chebyshev’s inequality tells us that
$|\mathrm{Vol}(\boldsymbol{f})-{\frac{1}{2}}|\geq{n\choose d}^{-1/12}$ with
probability at most $O({n\choose d}^{-1/6})=o(1),$ as claimed. ∎

###  4.2 Proof of Theorem 19

Given Lemma 21, to prove Theorem 19, it suffices to prove an $\Omega(n^{d/2})$
lower bound on the sample complexity of any algorithm $A$ that outputs “un-
truncated” with probability at least $9/10$ if it is given samples from
$\mathcal{D}_{u}$ and outputs “truncated” with probability at least $91/100$
if it is given samples from $\mathcal{D}_{u}|_{\boldsymbol{f}^{-1}(1)}$ where
$\boldsymbol{f}\sim\mathcal{F}_{d}$. We do this in the rest of this section
and start by introducing the “un-truncated” and “truncated” distributions that
we will show are hard to distinguish.

We will consider two different distributions ${\cal D}_{1}$ and ${\cal
D}_{2}$, each of which is a distribution over sequences of $m=c{n\choose
d}^{1/2}$ many points in $\\{-1,+1\\}^{n}$ where $c$ is an absolute constant
that we will set later. These distributions over sequences are defined as
follows:

  1. 1.

A draw of
$\overline{\boldsymbol{x}}=(\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(m)})$
from ${\cal D}_{1}$ is obtained by having each
$\boldsymbol{x}^{(i)}\in\mathbb{R}^{n}$ be drawn independently and uniformly
from $\mathcal{D}_{u}$.

  2. 2.

A draw of
$\overline{\boldsymbol{x}}=(\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(m)})$
from ${\cal D}_{2}$ is obtained by drawing (once and for all) a function
$\boldsymbol{f}\sim\mathcal{F}_{d}$ as described in Figure 1 and having each
$\boldsymbol{x}^{(i)}$ be distributed independently according to
$\mathcal{D}_{u}|_{\boldsymbol{f}}$, i.e. each $\boldsymbol{x}^{(i)}$ is drawn
from $\mathcal{D}_{u}$ conditioned on satisfying $\boldsymbol{p}(x^{(i)})\geq
0$.

We further define two more distributions ${\cal D}^{\prime}_{1}$ and ${\cal
D}^{\prime}_{2}$, each of which is a distribution over sequences of $3m$
points in $\\{-1,+1\\}^{n}\cup\\{0^{n}\\}$:

  1. 1.

A draw of
$\overline{\boldsymbol{x}}=(\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(3m)})$
from ${\cal D}^{\prime}_{1}$ is obtained as follows: $\boldsymbol{x}^{(i)}$ is
taken to be $\boldsymbol{b}_{i}\cdot\boldsymbol{u}^{(i)}$ where each
$\boldsymbol{b}_{i}$ is an independent uniform draw from $\\{0,1\\}$ and each
$\boldsymbol{u}^{(i)}$ is an independent draw from $\mathcal{D}_{u}$.

  2. 2.

A draw of
$\overline{\boldsymbol{z}}=(\boldsymbol{z}{(1)},\dots,\boldsymbol{z}^{(3m)})$
from ${\cal D}^{\prime}_{2}$ is obtained by drawing (once and for all) a
function $\boldsymbol{f}\sim\mathcal{F}_{d}$ as described in Figure 1 and
taking $\boldsymbol{z}^{(i)}$ to be
$\boldsymbol{f}(\boldsymbol{u}^{(i)})\cdot\boldsymbol{u}^{(i)}$, where each
$\boldsymbol{u}^{(i)}$ is an independent draw from $\mathcal{D}_{u}$.

The following claim shows that distinguishing $\mathcal{D}_{1}^{\prime}$ and
$\mathcal{D}_{2}^{\prime}$ is no harder than distinguishing $\mathcal{D}_{1}$
and $\mathcal{D}_{2}$.

######  Claim 23.

Suppose there exists an algorithm $A$ that successfully distinguishes between
${\cal D}_{1}$ and ${\cal D}_{2}$ (i.e. it outputs “un-truncated” with
probability at least 9/10 when run on a draw from ${\cal D}_{1}$ and outputs
“truncated” with probability at least 91/100 when run on a draw from ${\cal
D}_{2}$).

Then there exists an algorithm $A^{\prime}$ which successfully distinguishes
between ${\cal D}^{\prime}_{1}$ and ${\cal D}^{\prime}_{2}$ (i.e. it outputs
“un-truncated” with probability at least 89/100 when run on a draw from ${\cal
D}^{\prime}_{1}$ and outputs “truncated” with probability at least 90/100 when
run on a draw from ${\cal D}^{\prime}_{2}$).

###### Proof.

Let $A^{\prime}$ be the algorithm that simply takes the first $m$ non-$0^{n}$
points in its $3m$-point input sequence and uses them as input to $A$. We may
suppose that $A^{\prime}$ fails if there are fewer than $m$ non-$0^{n}$ points
in the $3m$-point sample: It is easy to see that whether the input to
$A^{\prime}$ is drawn from ${\cal D}^{\prime}_{1}$ or ${\cal D}^{\prime}_{2}$,
the probability of failure is at most $o(1)$ and hence is negligible; this
uses Lemma 21, i.e. the fact that in the no-case, with very high probability
$\boldsymbol{f}$ is roughly balanced.

We then have that

  * •

If the input sequence is a draw from ${\cal D}^{\prime}_{1}$ then the input
that $A^{\prime}$ gives to $A$ is distributed (up to statistical distance
$O(m/2^{n})$) according to ${\cal D}_{1}$. This statistical distance comes
because $A^{\prime}$ never passes the $0^{n}$-vector along as an input to $A$,
whereas under the distribution ${\cal D}_{1}$, each of the $m$ points has a
$1/2^{n}$ chance of being $0^{n}$; and

  * •

If the input is a draw from ${\cal D}^{\prime}_{2}$ then the input sequence
that $A^{\prime}$ gives to $A$ is distributed (up to statistical distance
$o(1)$) according to ${\cal D}_{2}$. This statistical distance comes from the
$o(1)$ chance that $\boldsymbol{f}$ has
$\mathrm{Vol}[\boldsymbol{f}]\notin[1/2-o(1),1/2+o(1)]$, plus the fact that
even if $\mathrm{Vol}[\boldsymbol{f}]\in[1/2-o(1),1/2+o(1)]$, algorithm
$A^{\prime}$ never passes along the 0-vector as an input to $A$.

This completes the proof of the claim. ∎

Given 23, to prove Theorem 19 it suffices to show that any algorithm
$A^{\prime}$ with the performance guarantee described above must have
$3m=\Omega(n^{d/2})$. This is a consequence of the following statement:

$\text{If $m=c{n\choose d}^{1/2}$, then~{}}\mathrm{d}_{\mathrm{TV}}({\cal
D}^{\prime}_{1},{\cal D}^{\prime}_{2})\leq 0.01.$ (23)

The rest of the proof establishes (23).

Consider a coupling of the two distributions ${\cal D}^{\prime}_{1}$ and
${\cal D}^{\prime}_{2}$ as follows. A draw from the joint coupled distribution
of $({\cal D}^{\prime}_{1},{\cal D}^{\prime}_{2})$ is generated in the
following way:

  * •

Let $(\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{3m})$ be a uniform random
string from $\\{0,1\\}^{3m}$, let $\boldsymbol{f}\sim\mathcal{F}_{d}$, and let
$\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)}$ be $3m$ independent draws
from $\mathcal{D}_{u}$.

  * •

The draw from the joint coupled distribution is
$(\overline{\boldsymbol{x}},\overline{\boldsymbol{z}})$ where

$\text{for each
$i=1,\dots,3m$,~{}~{}~{}}\boldsymbol{x}^{(i)}=\boldsymbol{b}_{i}\boldsymbol{u}^{(i)}\quad\text{and}\quad\boldsymbol{z}^{(i)}=\boldsymbol{f}(\boldsymbol{u}^{(i)})\boldsymbol{u}^{(i)}.$

It is easily verified that this is indeed a valid coupling of ${\cal
D}^{\prime}_{1}$ and ${\cal D}^{\prime}_{2}$. Writing
$\overline{\boldsymbol{u}}$ to denote
$(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(m)})$, we have that

$\displaystyle\mathrm{d}_{\mathrm{TV}}({\cal D}^{\prime}_{1},{\cal
D}^{\prime}_{2})$
$\displaystyle=\mathrm{d}_{\mathrm{TV}}((\boldsymbol{x}^{1},\dots,\boldsymbol{x}^{3m}),(\boldsymbol{z}^{1},\dots,\boldsymbol{z}^{3m}))$
$\displaystyle=\mathrm{d}_{\mathrm{TV}}\left((\boldsymbol{b}_{1}\boldsymbol{u}^{(1)},\dots,\boldsymbol{b}_{3m}\boldsymbol{u}^{(3m)}),\left(\boldsymbol{f}(\boldsymbol{u}^{(1)})\boldsymbol{u}^{(1)},\dots,\boldsymbol{f}(\boldsymbol{u}^{(3m)})\boldsymbol{u}^{(3m)}\right)\right)$
$\displaystyle\leq\mathop{{\bf
E}\/}_{\overline{\boldsymbol{u}}}\left[\mathrm{d}_{\mathrm{TV}}\left((\boldsymbol{b}_{1}\boldsymbol{u}^{(1)},\dots,\boldsymbol{b}_{3m}\boldsymbol{u}^{(3m)}),\left(\boldsymbol{f}(\boldsymbol{u}^{(1)})\boldsymbol{u}^{(1)},\dots,\boldsymbol{f}(\boldsymbol{u}^{(3m)})\boldsymbol{u}^{(3m)}\right)\right)\right]$
(24) $\displaystyle=\mathop{{\bf
E}\/}_{\overline{\boldsymbol{u}}}\left[\mathrm{d}_{\mathrm{TV}}\left((\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{3m}),\left(\boldsymbol{f}(\boldsymbol{u}^{(1)}),\dots,\boldsymbol{f}(\boldsymbol{u}^{(3m)})\right)\right)\right],$
(25)

where $\boldsymbol{b}=(\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{3m})$ is
uniform over $\\{0,1\\}^{3m}$; it should be noted that in Equation 24 the
randomness in the two random variables whose variation distance is being
considered is only over $\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{m}$ and
$\boldsymbol{p}$.

It remains to show that if $m=c{n\choose d}^{1/2}$ then
$(\ref{eq:pumpkin})\leq 0.01;$ this is equivalent to showing that

$\mathop{{\bf
E}\/}_{\overline{\boldsymbol{u}}}\left[\mathrm{d}_{\mathrm{TV}}\left((\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{3m}),{\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot\Phi(\boldsymbol{u}^{i})\geq
0\right\\}}\right)}_{i=1}^{3m}\right)\right]\leq 0.01,$ (26)

and this is what we establish in the rest of the proof. (Recall that
$\boldsymbol{f}(x)=\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot\Phi(x)\geq
0\right\\}}$.)

For $S\in{[n]\choose d}$ we write $e_{S}$ to denote the canonical basis vector
in $\mathbb{R}^{{n\choose d}}$ that has a 1 in the $S$-th position and 0’s in
all other positions. We observe that for $\widehat{\boldsymbol{p}}\sim
N(0,1)^{{n\choose d}}$, for any fixed $S\in{[n]\choose d}$ we have that

$\operatorname{{\bf Pr}}\left[\widehat{\boldsymbol{p}}\cdot e_{S}\geq
0\right]=\operatorname{{\bf Pr}}\left[\widehat{\boldsymbol{p}}(S)\geq
0\right]=1/2.$

Let $S_{1},\dots,S_{{n\choose d}}$ be some fixed ordering, say lexicographic,
of the ${n\choose d}$ elements of ${[n]\choose d}$. Since the random variables
$(\widehat{\boldsymbol{p}}(S_{i}))_{i=1,\dots,3m}$ are independent, we have
that the joint distribution of
$(\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{3m})$ is identical to the joint
distribution of $(\mathrm{sign}(\widehat{\boldsymbol{p}}\cdot
e_{S_{1}}),\dots,\mathrm{sign}(\widehat{\boldsymbol{p}}\cdot e_{S_{3m}}))$,
namely both distributions are uniform over $\\{0,1\\}^{3m}.$ Thus we have that

$\displaystyle(\ref{eq:squash})$ $\displaystyle=\mathop{{\bf
E}\/}_{\overline{\boldsymbol{u}}}\left[\mathrm{d}_{\mathrm{TV}}\left({\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot
e_{S_{i}}\right\\}}\geq
0\right)}_{i=1}^{3m},{\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot\Phi(\boldsymbol{u}^{i})\geq
0\right\\}}\right)}_{i=1}^{3m}\right)\right]$ (27)

where as in the proof of Lemma 21, we define

$\Phi\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\mathbb{R}^{n\choose
d}\qquad\text{as}\qquad\Phi(x)={\left(x_{S}\right)}_{S\in{[n]\choose d}}.$

In the rest of the argument, we show that the right hand side of Equation 27
is small by arguing that for most outcomes $(u^{(1)},\dots,u^{(3m)})$ of
$(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)})$, the covariance
structures of the two $3m$-dimensional Gaussians
$(\widehat{\boldsymbol{p}}\cdot e_{S_{1}},\dots,\widehat{\boldsymbol{p}}\cdot
e_{S_{3m}})$ and
$(\widehat{\boldsymbol{p}}\cdot\Phi(u^{(1)}),\dots,\widehat{\boldsymbol{p}}\cdot\Phi(u^{(3m)}))$
are similar enough that it is possible to bound the variation distance between
those two Gaussians, which implies a bound on the variation distance between
the two vector-valued random variables on the right hand side of Equation 27.

######  Definition 24.

Fix a specific outcome $(u^{(1)},\dots,u^{(3m)})\in(\\{-1,+1\\}^{n})^{3m}$ of
$(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)})\sim(\\{-1,+1\\}^{n})^{3m}$.
Let $\Sigma_{2}$ be the $3m\times 3m$ matrix whose $(i,j)$ entry is
$\Phi^{\prime}(u^{(i)})\cdot\Phi^{\prime}(u^{(j)})$, let $I_{3m}$ be the
$3m\times 3m$ identity matrix, and let $A=\Sigma_{2}-I_{3m}.$ We say that
$(u^{(1)},\dots,u^{(3m)})$ is _bad_ if
$\mathrm{tr}(A^{2})\geq{\frac{1}{90000}}$; otherwise we say that
$(u^{(1)},\dots,u^{(3m)})$ is _good_.

Intuitively, the tuple $(u^{(1)},\dots,u^{(m)})$ is bad if the $3m$ vectors
$\Phi(u^{(1)}),\dots,\Phi(u^{3m})$ are not such that “most pairs are close to
orthogonal to each other” (recall that each vector $\Phi(u^{(i)})$ is
${n\choose d}$-dimensional). As we now show, this is very unlikely to happen
for
$(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)})\sim(\\{-1,+1\\}^{n})^{3m}$.

######  Claim 25.

For $m=c{n\choose d}^{1/2}$, we have $\operatorname{{\bf
Pr}}[(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)})$ is bad$]\leq 0.005.$

###### Proof.

The idea is to apply Chebyshev’s inequality to the random variable
$\mathrm{tr}(A(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)}))$. In more
detail, we observe that
$\mathrm{tr}(A(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)})^{2})$ is a
polynomial in the $3mn$ uniform random Boolean variables
$\boldsymbol{u}^{(r)}_{s}$. Let’s start by working out what this polynomial is
(for notational ease, let’s write $q=q(u)$ for this polynomial). Since
$\Phi^{\prime}(u^{(i)})$ is a unit vector for all $i$ for every outcome
$u^{(i)}$ of $\boldsymbol{u}^{(i)}$, the diagonal entries of $A$ are zero. For
$i\neq j$, the entry $A_{ij}$ is

$A_{ij}={\frac{\Phi(u^{(i)})\cdot\Phi(u^{(j)})}{{n\choose
d}}}={\frac{\sum_{S\in{[n]\choose d}}u^{(i)}_{S}u^{(j)}_{S}}{{n\choose d}}},$
(28)

so the diagonal element $(A^{2})_{ii}$ of $A^{2}$ is

$\displaystyle(A^{2})_{ii}$
$\displaystyle=\sum_{j=1}^{3m}A_{ij}A_{ji}=\sum_{j\in[3m]\setminus\\{i\\}}A_{ij}^{2}$
$\displaystyle=\sum_{j\in[3m]\setminus\\{i\\}}{\frac{1}{{n\choose
d}^{2}}}\sum_{S,T\in{{[n]\choose
d}}}u^{(i)}_{S\,\triangle\,T}u^{(j)}_{S\,\triangle\,T},$ (29)

and

$\displaystyle q(u)=\mathrm{tr}(A^{2})$
$\displaystyle=\sum_{i=1}^{3m}\sum_{j\in[3m]\setminus\\{i\\}}{\frac{1}{{n\choose
d}^{2}}}\sum_{S,T\in{{[n]\choose
d}}}u^{(i)}_{S\,\triangle\,T}u^{(j)}_{S\,\triangle\,T}.$ (30)

From (30) we see that $\mathrm{tr}(A^{2})=q$ is a polynomial of degree at most
$4d$ (since $|S\,\triangle\,T|$ is always at most $2d$), and that the constant
term of $q$ is

$\operatorname{{\bf
E}}[q]=\widehat{q}(\emptyset)=3m(3m-1)\cdot{\frac{1}{{n\choose
d}^{2}}}\cdot{n\choose d},$

which is at most $9c^{2}$ recalling that $m=c{n\choose d}^{1/2}.$ We choose
the constant $c$ so that $9c^{2}\leq{\frac{1}{180000}}$, so
$\operatorname{{\bf E}}[q]\leq{\frac{1}{180000}}$; we want to show that for a
random $\boldsymbol{u}=(\boldsymbol{u}^{(i)}_{j})$, the probability that
$q(\boldsymbol{u})$ exceeds its mean by ${\frac{1}{180000}}$ is at most a
constant. To do this, let us bound the variance of $q$, i.e. the sum of
squares of its non-constant coefficients.

Note that in Equation 30, we have that every non-constant coefficient is on a
monomial of the form $u^{(i)}_{U}u^{(j)}_{U}$ for some $i\neq j$ where
$U\subseteq[n]$ and $|U|=\mathrel{\mathop{\mathchar 58\relax}}k\leq 2d.$
Recall from Lemma 17, the number of $(S,T)$ pairs with $|S|,|T|=d$ such that
$S\,\triangle\,T=U$ is at most

$O_{d}{\left(n^{d-{\left\lceil k/2\right\rceil}}\right)}.$

So the coefficient of $u^{(i)}_{C}u^{(j)}_{C}$ is

$\widehat{q}(i,j,C)\leq{\frac{O_{d}{\left(n^{d-{\left\lceil
k/2\right\rceil}}\right)}}{{n\choose d}^{2}}}.$

As there are at most ${n\choose k}$ sets $U\subseteq[n]$ with $|U|=k$, we have

$\displaystyle\operatorname{{\bf Var}}[q]$ $\displaystyle\leq
9m^{2}\sum_{k=1}^{2d}{n\choose k}\cdot\widehat{q}(i,j,C)^{2}$
$\displaystyle\leq 9m^{2}\sum_{k=1}^{2d}{n\choose
k}\cdot{\left(\frac{O_{d}{\left(n^{d-{\left\lceil
k/2\right\rceil}}\right)}}{{n\choose d}^{2}}\right)}^{2}$ $\displaystyle\leq
O_{d}{\left(9m^{2}\sum_{k=1}^{2d}\frac{n^{k}\cdot n^{2d-k}}{n^{4d}}\right)}$
$\displaystyle\leq O_{d}{\left(\frac{1}{n^{d}}\right)},$

where the final inequality relies on our choice of
$m\mathrel{\mathop{\mathchar 58\relax}}=c{n\choose d}^{1/2}$. Putting
everything together, we have that

$\operatorname{{\bf
E}}[q]\leq{\frac{1}{180000}}\qquad\text{and}\qquad\sqrt{\operatorname{{\bf
Var}}[q]}\leq O_{d}{\left(\frac{1}{n^{d/2}}\right)}.$

By Chebyshev’s inequality, we get

$\operatorname{{\bf Pr}}{\left[q\geq{\frac{1}{90000}}\right]}\leq
O{\left(\frac{1}{n^{d}}\right)}$

which is at most $0.005$ for sufficiently large $n$. In particular, this
implies that for $n$ large enough, we have $\operatorname{{\bf
Pr}}[(\boldsymbol{u}^{(1)},\dots,\boldsymbol{u}^{(3m)})$ is bad$]\leq 0.005$,
completing the proof. ∎

Hence to show that $(\ref{eq:rigatoni})\leq 0.01$ (and finish the proof of
Theorem 19), it suffices to prove the following:

######  Claim 26.

Fix a good $(u^{(1)},\dots,u^{(3m)})\in(\\{-1,+1\\}^{n})^{3m}$. Then for
$\widehat{\boldsymbol{p}}\sim N(0,1)^{n\choose d}$ we have that

$\mathrm{d}_{\mathrm{TV}}\left({\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot
e_{S_{i}}\right\\}}\geq
0\right)}_{i=1}^{3m},{\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot\Phi(\boldsymbol{u}^{i})\geq
0\right\\}}\right)}_{i=1}^{3m}\right)\leq 0.005.$ (31)

To prove 26 we first observe that (31) is equivalent to

$\mathrm{d}_{\mathrm{TV}}\left({\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot
e_{S_{i}}\right\\}}\geq
0\right)}_{i=1}^{3m},{\left(\mathbf{1}{\left\\{\widehat{\boldsymbol{p}}\cdot\Phi^{\prime}(u^{i})\geq
0\right\\}}\right)}_{i=1}^{3m}\right)\leq 0.005$ (32)

where (as in the proof of Lemma 21) we define
$\Phi^{\prime}(u^{(i)})\mathrel{\mathop{\mathchar
58\relax}}=\Phi(u^{(i)})/\|\Phi(u^{(i)})\|=\Phi(u^{(i)})/\sqrt{{n\choose d}}$
to be $\Phi(u^{(i)})$ normalized to unit length. We now apply Theorem 20 where
we take $k=3m$, $\Sigma_{1}$ to be the identity matrix $I_{3m},$ and
$\Sigma_{2}$ to be the $3m\times 3m$ matrix whose $(i,j)$ entry is
$\Phi^{\prime}(u^{(i)})\cdot\Phi^{\prime}(u^{(j)})$, so a draw from
$N(0,\Sigma_{1})$ is distributed as $(\widehat{\boldsymbol{p}}\cdot
e_{1},\dots,\widehat{\boldsymbol{p}}\cdot e_{3m})$ and a draw from
$N(0,\Sigma_{2})$ is distributed as
$(\widehat{\boldsymbol{p}}\cdot\Phi^{\prime}(u^{(1)}),\dots,\widehat{\boldsymbol{p}}\cdot\Phi^{\prime}(u^{(3m)})).$
Applying the data processing inequality for total variation distance (see e.g.
Proposition B.1 of [DDO+13]), it follows that the LHS of (32) is at most
$\mathrm{d}_{\mathrm{TV}}(N(0^{3m},\Sigma_{1}),N(0^{3m},\Sigma_{2}))$; we
proceed to upper bound the RHS of Theorem 20.

Let $A$ denote the matrix $\Sigma_{1}^{-1}\Sigma_{2}-I_{3m}$, so
$\lambda_{1}^{2},\dots,\lambda_{3m}^{2}$ are the eigenvalues of $A^{2}$ and we
have
$\sqrt{\lambda_{1}^{2}+\cdots+\lambda_{3m}^{2}}=\sqrt{\mathrm{tr}(A^{2}))}.$
Since $A$ is good we have that $\mathrm{tr}(A^{2})\leq{\frac{1}{90000}}$,
which gives that
${\frac{3}{2}}\cdot\min\left\\{1,\sqrt{\lambda_{1}^{2}+\cdots+\lambda_{m}^{2}}\right\\}\leq
0.05$ as required, and the proofs of 26, Equation 26, and Theorem 19 are
complete.

## Acknowledgements

A.D. is supported by NSF grants CCF-1910534, CCF-1926872, and CCF-2045128.
H.L. is supported by NSF grants CCF-1910534, CCF-1934876, and CCF-2008305.
S.N. is supported by NSF grants IIS-1838154, CCF-2106429, CCF-2211238,
CCF-1763970, and CCF-2107187. Part of this work was completed while S.N. was
participating in the program on “Meta Complexity” at the Simons Institute for
the Theory of Computing. R.A.S. is supported by NSF grants IIS-1838154,
CCF-2106429, and CCF-2211238. The authors would like to thank the anonymous
STOC reviewers for helpful comments.

## References

  * [AAR99] George E Andrews, Richard Askey, and Ranjan Roy.  Special functions, volume 71.  Cambridge University Press, Cambridge, 1999.
  * [AB02] M. Anthony and P. L. Bartlett.  Neural Network Learning - Theoretical Foundations.  Cambridge University Press, 2002.
  * [ABFR94] J. Aspnes, R. Beigel, M. Furst, and S. Rudich.  The expressive power of voting polynomials.  Combinatorica, 14(2):1–14, 1994.
  * [AH09] Per Austrin and Johan Håstad.  Randomly supported independence and resistance.  In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), pages 483–492. ACM, 2009.
  * [Ant95] Martin Anthony.  Classification by polynomial surfaces.  Discrete Applied Mathematics, 61(2):91–103, 1995.
  * [AS17] Guillaume Aubrun and Stanisław J. Szarek.  Alice and Bob meet Banach, volume 223 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2017.  The interface of asymptotic geometric analysis and quantum information theory.
  * [BC14] N. Balakrishnan and Erhard Cramer.  The art of progressive censoring.  Springer, 2014.
  * [BDNP21] Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas.  Efficient statistics for sparse graphical models from truncated samples.  In International Conference on Artificial Intelligence and Statistics, pages 1450–1458. PMLR, 2021.
  * [BHYY22] Omri Ben-Eliezer, Max Hopkins, Chutong Yang, and Hantao Yu.  Active learning polynomial threshold functions.  CoRR, abs/2201.09433, 2022.
  * [BL76a] H. Brascamp and E. Lieb.  Best constants in Young’s Inequality, its converse and its generalization to more than three functions.  Advances in Mathematics, 20:151–172, 1976.
  * [BL76b] H. Brascamp and E. Lieb.  On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log-concave functions and with an application to the diffusion equation.  Journal of Functional Analysis, 22:366–389, 1976.
  * [Bor85] C. Borell.  Geometric bounds on the Ornstein-Uhlenbeck velocity process.  Probability Theory and Related Fields, 70:1–13, 1985.
  * [BS92] J. Bruck and R. Smolensky.  Polynomial threshold functions, AC0 functions and spectral norms.  SIAM Journal on Computing, 21(1):33–42, 1992.
  * [BS14] T. Bloom and B. Shiffman.  Zeros of random polynomials on $\mathbb{C}^{m}$.  Math Res. Lett., 14:469–479, 2014.
  * [BV19] Pierre Baldi and Roman Vershynin.  Polynomial threshold functions, hyperplane arrangements, and random tensors.  SIAM Journal on Mathematics of Data Science, 1(4):699–729, 2019\.
  * [CDS20] Clément L. Canonne, Anindya De, and Rocco A. Servedio.  Learning from satisfying assignments under continuous distributions.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 82–101. SIAM, 2020.
  * [Cha02] Mei-Chu Chang.  A polynomial bound in Freiman’s theorem.  Duke Mathematical Journal, 113(3):399 – 419, 2002.
  * [Coh16] A. Clifford Cohen.  Truncated and censored samples: theory and applications.  CRC Press, 2016.
  * [Con19] John B Conway.  A course in functional analysis, volume 96.  Springer, 2019.
  * [DDO+13] C. Daskalakis, I. Diakonikolas, R. O’Donnell, R. A. Servedio, and L.-Y. Tan.  Learning sums of independent integer random variables.  In 54th Annual IEEE Symposium on Foundations of Computer Science, pages 217–226, 2013.
  * [DDS14] Anindya De, Ilias Diakonikolas, and Rocco A. Servedio.  Deterministic approximate counting for juntas of degree-2 polynomial threshold functions.  In Proceedings of the 29th Annual Conference on Computational Complexity (CCC), pages 229–240. IEEE, 2014.
  * [DDS15] A. De, I. Diakonikolas, and R. A. Servedio.  Learning from satisfying assignments.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages 478–497, 2015.
  * [DFKO06] Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell.  On the Fourier tails of bounded functions over the discrete cube.  In Proc. 38th ACM Symp. on Theory of Computing, pages 437–446, 2006\.
  * [DGL05] F. Denis, R. Gilleron, and F. Letouzey.  Learning from positive and unlabeled examples.  Theor. Comput. Sci., 348(1):70–83, 2005.
  * [DGTZ18] C. Daskalakis, T. Gouleakis, C. Tzamos, and M. Zampetakis.  Efficient statistics, in high dimensions, from truncated samples.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 639–649. IEEE Computer Society, 2018.
  * [DGTZ19] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis.  Computationally and statistically efficient truncated regression.  In Conference on Learning Theory (COLT), volume 99 of Proceedings of Machine Learning Research, pages 955–960, 2019.
  * [DKN10] Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson.  Bounded independence fools degree-2 threshold functions.  In Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS), pages 11–20, 2010.
  * [DKP22] Ilias Diakonikolas, Daniel M. Kane, and Ankit Pensia.  Gaussian mean testing made simple.  CoRR, abs/2210.13706, 2022.
  * [DKPZ21] Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis.  The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 1552–1584. PMLR, 2021.
  * [DMR20] Luc Devroye, Abbas Mehrabian, and Tommy Reddad.  The total variation distance between high-dimensional gaussians.  arXiv:1810.08693v5, 22 May 2020, 2020.
  * [DNS22] Anindya De, Shivam Nadimpalli, and Rocco A. Servedio.  Convex influences.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS, volume 215 of LIPIcs, pages 53:1–53:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [DNS23] Anindya De, Shivam Nadimpalli, and Rocco A. Servedio.  Testing Convex Truncation.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4050–4082. 2023.
  * [DOSW11] I. Diakonikolas, R. O’Donnell, R. Servedio, and Y. Wu.  Hardness results for agnostically learning low-degree polynomial threshold functions.  In SODA, pages 1590–1606, 2011.
  * [DRST14] Ilias Diakonikolas, Prasad Raghavendra, Rocco A Servedio, and Li-Yang Tan.  Average sensitivity and noise sensitivity of polynomial threshold functions.  SIAM Journal on Computing, 43(1):231–253, 2014.
  * [DRZ20] C. Daskalakis, D. Rohatgi, and E. Zampetakis.  Truncated linear regression in high dimensions.  Advances in Neural Information Processing Systems, 33:10338–10347, 2020.
  * [DS14] Anindya De and Rocco A. Servedio.  Efficient deterministic approximate counting for low-degree polynomial threshold functions.  In Proceedings of the 46th Annual Symposium on Theory of Computing (STOC), pages 832–841, 2014.
  * [DSYZ21] C. Daskalakis, P. Stefanou, R. Yao, and E. Zampetakis.  Efficient truncated linear regression with unknown noise variance.  Advances in Neural Information Processing Systems, 34:1952–1963, 2021.
  * [Fis31] R.A. Fisher.  Properties and applications of HH functions.  In Mathematical tables, pages 815–852, 1931.
  * [FKT20] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos.  Efficient parameter estimation of truncated boolean product distributions.  In Conference on Learning Theory (COLT), volume 125 of Proceedings of Machine Learning Research, pages 1586–1600, 2020.
  * [Gal97] Francis Galton.  An examination into the registered speeds of American trotting horses, with remarks on their value as hereditary data.  Proceedings of the Royal Society of London, 62(379-387):310–315, 1897.
  * [GL94] C. Gotsman and N. Linial.  Spectral properties of threshold functions.  Combinatorica, 14(1):35–50, 1994.
  * [Ham56] J. Hammersley.  The zeros of a random polynomial.  In Proc. Third Berkeley Symposium on Probability and Statistics, volume 2, pages 89–111, 1956.
  * [HKM14] Prahladh Harsha, Adam Klivans, and Raghu Meka.  Bounding the sensitivity of polynomial threshold functions.  Theory of Computing, 10(1):1–26, 2014.
  * [Hoe94] Wassily Hoeffding.  A class of statistics with asymptotically normal distribution.  The Collected Works of Wassily Hoeffding, pages 171–204, 1994.
  * [IZ97] I. Ibragimov and O. Zeitouni.  On roots of random polynomials.  Transactions of the American Mathematical Society, 349(6):2427–2441, 1997.
  * [Kan11a] Daniel Kane.  $k$-independent Gaussians fool polynomial threshold functions.  In Proceedings of the 26th Conference on Computational Complexity (CCC), pages 252–261, 2011.
  * [Kan11b] Daniel Kane.  A small PRG for polynomial threshold functions of Gaussians.  In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 257–266, 2011.
  * [Kan12] D. Kane.  A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 91–100, 2012.
  * [Kan13] Daniel M Kane.  The correct exponent for the gotsman-linial conjecture.  In 2013 IEEE Conference on Computational Complexity, pages 56–64. IEEE, 2013.
  * [Kan14a] D. M. Kane.  The correct exponent for the Gotsman-Linial Conjecture.  Computational Complexity, 23(2):151–175, 2014.
  * [Kan14b] Daniel Kane.  A pseudorandom generator for polynomial threshold functions of Gaussians with subpolynomial seed length.  In Proceedings of the 29th Annual Conference on Computational Complexity (CCC), pages 217–228, 2014.
  * [Kan15] D. M. Kane.  A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting.  In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 567–581, 2015.
  * [KKL17] Valentine Kabanets, Daniel M Kane, and Zhenjian Lu.  A polynomial restriction lemma with applications.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 615–628, 2017.
  * [KL18] Valentine Kabanets and Zhenjian Lu.  Satisfiability and Derandomization for Small Polynomial Threshold Circuits.  In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), volume 116, pages 46:1–46:19, 2018.
  * [KM13] Daniel M. Kane and Raghu Meka.  A prg for lipschitz functions of polynomials with applications to sparsest cut.  In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 1–10, New York, NY, USA, 2013. Association for Computing Machinery.
  * [KR18] Daniel Kane and Sankeerth Rao.  A PRG for Boolean PTF of degree 2 with seed length subpolynomial in $\varepsilon$ and logarithmic in $n$.  In Proceedings of the 33rd Computational Complexity Conference (CCC), pages 2:1–2:24, 2018.
  * [KTZ19] Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis.  Efficient truncated statistics with unknown truncation.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1578–1595. IEEE Computer Society, 2019.
  * [KV94] M. Kearns and U. Vazirani.  An Introduction to Computational Learning Theory.  MIT Press, Cambridge, MA, 1994.
  * [Lee14] Alice Lee.  Table of the Gaussian “Tail” Functions; When the “Tail” is Larger than the Body.  Biometrika, 10(2/3):208–214, 1914.
  * [MZ13] R. Meka and D. Zuckerman.  Pseudorandom Generators for Polynomial Threshold Functions.  SIAM J. Comput., 42(3):1275–1301, 2013.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [OST20] Ryan O’Donnell, Rocco A. Servedio, and Li-Yang Tan.  Fooling gaussian ptfs via local hyperconcentration.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1170–1183. ACM, 2020\.
  * [Pea02] Karl Pearson.  On the systematic fitting of frequency curves.  Biometrika, 2:2–7, 1902.
  * [Sak93] M. Saks.  Slicing the hypercube.  In Keith Walker, editor, Surveys in Combinatorics 1993, pages 211–257. London Mathematical Society Lecture Note Series 187, 1993.
  * [Sch86] Helmut Schneider.  Truncated and censored samples from normal populations.  Marcel Dekker, Inc., 1986.
  * [ST18] Rocco A. Servedio and Li-Yang Tan.  Luby-velickovic-wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits.  In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (APPROX/RANDOM), volume 116 of LIPIcs, pages 56:1–56:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [Tal96] M. Talagrand.  How much are increasing sets positively correlated?  Combinatorica, 16(2):243–258, 1996.
  * [VC71] VN Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  Theory of Probability and its Applications, 16(2):264, 1971.
  * [Vem10] Santosh S. Vempala.  Learning convex concepts from gaussian distributions with PCA.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 124–130. IEEE Computer Society, 2010.
  * [Wol07] Paweł Wolff.  Hypercontractivity of simple random variables.  Studia Mathematica, 3:219–236, 2007.

##  Appendix A Testing Truncation via VC Dimension

In this section, we show that $O_{d}(n^{d}/\varepsilon^{2})$ samples are
sufficient for distinguishing an unknown distribution $\mathcal{P}$ over
$\mathbb{R}^{n}$ from $\mathcal{P}|_{f^{-1}(1)}$ where
$f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\to\\{0,1\\}$ is a
degree-$d$ PTF with $\mathrm{Vol}(f)\leq 1-\varepsilon$. This follows
immediately from the following more general result which allows us to test
truncation by an unknown function belonging to a concept class $\mathcal{C}$
with sample complexity linear in the _VC-dimension_ of the class $\mathcal{C}$
(denoted $\mathrm{VC\text{-}Dim}(\mathcal{C})$; we refer the reader to [KV94]
for background on VC-dimension) and bounds on the VC-dimension of degree-$d$
PTFs over $\mathbb{R}^{n}$ (Corollary 9 of [Ant95]). As mentioned in the
introduction, the algorithm used to prove Proposition 27 is not time-
efficient.

######  Proposition 27.

Let ${\mathcal{P}}$ be an arbitrary probability distribution over
$\mathbb{R}^{n}$. Let $\mathcal{C}$ be a class of $0/1$-valued functions on
$\mathbb{R}^{n}$ such that each $f\in\mathcal{C}$ satisfies

$\mathrm{Vol}(f)\leq 1-\varepsilon.$

There exists an algorithm with the following properties: The algorithm is
given access to i.i.d. samples from an unknown distribution $\mathcal{D}$ with

$\mathcal{D}\in{\left\\{\mathcal{P}\right\\}}\cup{\left\\{\mathcal{P}|_{f^{-1}(1)}\mathrel{\mathop{\mathchar
58\relax}}f\in\mathcal{C}\right\\}}.$

It draws
$\Theta{\left(\mathrm{VC\text{-}Dim}(\mathcal{C})/\varepsilon^{2}\right)}$
samples from $\mathcal{D}$, and has the following performance guarantee:

  1. 1.

If $\mathcal{D}=\mathcal{P}$, then the algorithm outputs “un-truncated” with
probability at least $2/3$; and

  2. 2.

If $\mathcal{D}=\mathcal{P}|_{f^{-1}(1)}$ for some $f\in\mathcal{C}$, then the
algorithm outputs “truncated” with probability 1.

###### Proof.

Consider the following simple algorithm:

  1. 1.

Draw $T\mathrel{\mathop{\mathchar
58\relax}}=\Theta{\left(\frac{\mathrm{VC\text{-}Dim}(\mathcal{C})}{\varepsilon^{2}}\right)}$
samples $\\{\boldsymbol{x}^{(1)},\ldots,\boldsymbol{x}^{(T)}\\}$ from
$\mathcal{D}$.

  2. 2.

If there exists a function $f\in\mathcal{C}$ such that
$f(\boldsymbol{x}^{(i)})=1$ for all $i\in[T]$, output “truncated.” Otherwise,
output “untruncated.”

If $\mathcal{D}=\mathcal{P}|_{f^{-1}(1)}$ for some $f\in\mathcal{C}$, then the
algorithm will clearly always output “truncated.” It remains to show that when
$\mathcal{D}=\mathcal{P}$, the algorithm outputs “truncated” with probability
at most $1/3$. As $\mathrm{Vol}(f)\leq 1-\varepsilon$ for all
$f\in\mathcal{C}$, we have that for any fixed $f\in\mathcal{C}$ the following
holds by linearity of expectation:

$\mathop{{\bf
E}\/}_{\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(T)}\sim\mathcal{P}}{\left[\frac{\\#{\left\\{i\mathrel{\mathop{\mathchar
58\relax}}f(\boldsymbol{x}^{(i)})=1\right\\}}}{T}\right]}\leq 1-\varepsilon.$

By a standard application of the VC inequality [VC71] (see e.g. Theorem 4.3 of
[AB02]) and recalling our choice of $T$, we get that

$\mathop{{\bf
Pr}\/}_{\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(T)}\sim\mathcal{P}}{\left[\frac{1}{T}\cdot\sup_{f\in\mathcal{C}}{\\#{\left\\{i\mathrel{\mathop{\mathchar
58\relax}}f(\boldsymbol{x}^{(i)})=1\right\\}}}\geq
1-\frac{\varepsilon}{4}\right]}\leq 0.01.$

In particular, this implies that with probability at least 99/100, no function
$f\in\mathcal{C}$ is consistent with $f(\boldsymbol{x}^{(i)})$ for $i\in[T]$
when $\mathcal{D}=\mathcal{P}$, completing the proof. ∎

##  Appendix B An $\Omega(n^{d/4})$-Sample Lower Bound for Testing Low-Volume
PTF Truncation

In this section, we give a simple lower bound of $\Omega(n^{d/4})$-samples to
test PTF truncation. In more detail, we show that at least
$\Omega(n^{d/4})$-samples are required to distinguish the uniform distribution
on the Boolean hypercube $\\{-1,+1\\}^{n}$ from the uniform distribution on
$\\{-1,+1\\}^{n}$ truncated by a _low-volume_ degree-$d$ PTF; the volume of
the truncating PTF is in fact be only $\Theta(n^{d/2}/2^{n})$.

Towards this, we first recall a useful lemma due to Aspnes et al. [ABFR94]
(whose proof only uses basic linear algebra):

######  Lemma 28 ([ABFR94], Lemma 2.1).

Let $S$ be a set of points in $\\{-1,1\\}^{n}$ such that
$|S|<\sum_{i=0}^{d/2}\binom{n}{i}$ for some even number $0<d\leq n$. Then
there exists a degree-$d$ PTF $f$ whose satisfying assignments are precisely
the points in $S$, i.e. $f(x)=1$ for all $x\in S$ and $f(x)=0$ for all
$\boldsymbol{x}\notin S$.

We now present our lower bound and its proof.

######  Proposition 29.

Let ${\cal U}$ be the uniform distribution over $\\{-1,+1\\}^{n}$. Fix any
constant $d$, and let $\mathcal{C}_{\mathrm{PTF}}^{\ast}$ be the class of
Boolean functions on $\\{-1,+1\\}^{n}$ such that each
$f\in\mathcal{C}_{\mathrm{PTF}}^{\ast}$ is a degree-$d$ PTF
$f\mathrel{\mathop{\mathchar 58\relax}}\\{-1,+1\\}^{n}\to\\{0,1\\}$ with

$\mathrm{Vol}(f)={\frac{|f^{-1}(1)|}{2^{n}}}=\Theta(n^{d/2}/2^{n}).$

Let $A$ be any algorithm with the following property: Given sample access to
an unknown distribution $\mathcal{D}$ with

$\mathcal{D}\in\\{\mathcal{U}\\}\cup{\left\\{\mathcal{U}|_{f^{-1}(1)}\mathrel{\mathop{\mathchar
58\relax}}f\in\mathcal{C}_{\mathrm{PTF}}^{\ast}\right\\}},$

$A$ has the following performance guarantee:

  1. 1.

If $\mathcal{D}=\mathcal{U}$, then $A$ outputs “un-truncated” with probability
$2/3$; and

  2. 2.

If $\mathcal{D}=\mathcal{U}|_{f^{-1}(1)}$ for some
$f\in\mathcal{C}_{\mathrm{PTF}}^{\ast}$, then $A$ outputs “truncated” with
probability $2/3$.

Then $A$ must use at least $\Omega(n^{d/4})$ samples from $\mathcal{D}$.

###### Proof.

Consider choosing a degree-$d$ PTF over $\\{-1,+1\\}^{n}$ as follows:

  1. 1.

First, draw a collection $\boldsymbol{S}$ of
$N_{d/2}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{i=0}^{d/2}{n\choose
i}-1=\Theta(n^{d/2})$ random points from $\\{-1,+1\\}^{n}$.

  2. 2.

Let $\boldsymbol{f}$ be a degree-$d$ PTF such that

$\boldsymbol{f}(x)=\begin{cases}1&x\in\boldsymbol{S}\\\
0&x\notin\boldsymbol{S}\end{cases}.$

Note that the existence of such an $\boldsymbol{f}$ is guaranteed by Lemma 28.

We will now show that no algorithm $A$ that draws $m=cn^{d/4}$ samples, for a
sufficiently small absolute constant $c>0$, can distinguish between
$\mathcal{U}$ and $\mathcal{U}|_{\boldsymbol{f}^{-1}(1)}$ with probability
$2/3$, from which the result is immediate. When $\mathcal{D}=\mathcal{U}$,
then note that the $m$ samples are distribution independently and uniformly
over $\\{-1,+1\\}^{n}$. On the other hand, when
$\mathcal{D}=\mathcal{U}|_{\boldsymbol{f}^{-1}(1)}$, then (i) by a standard
application of the birthday paradox, since
$|\boldsymbol{f}^{-1}(1)|\geq\Omega(n^{d/2})$, the $m$ samples are all
distinct except with an arbitrarily small constant probability (depending on
$c$); and (ii) conditioned on all the samples being distinct, they are also
uniformly distributed over $\\{-1,+1\\}^{n}$ as the support of
$\boldsymbol{f}$ (namely $\boldsymbol{S}$) was chosen at random.

It follows from (i) and (ii) that the total variation distance between
$\mathcal{U}$ and $\mathcal{U}|_{\boldsymbol{f}^{-1}(1)}$ is at most an
arbitrarily small constant, as needed to be shown. ∎