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 datanamely, 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 D is the standard multidimensional normal distribution N (0, 1) n and the truncation set is assumed to be an unknown convex set in 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/ε 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 -ε; and (ii) a Ω( √ 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 D over 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 : R n → {0, 1} is a degree-d polynomial threshold function (PTF) if there is a real multivariate polynomial p(x) with deg(p) ≤ d such that f (x) = 1 if and only if p(x) ≥ 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.

To set the stage for our algorithmic results, we begin with the following observation: Observation 1. For any fixed ("known") background distribution P over R n , O d (n d /ε 2 ) samples from an unknown distribution D are sufficient to distinguish (with high probability) between the two cases that (i) D is the original distribution P, versus (ii) D is P | f , i.e. P conditioned on f -1 (1), where f is an unknown degree-d PTF satisfying

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 R n is O(n d ). For the sake of completeness, we give a proof in Appendix A of the full version of this paper.

While the above observation works for any fixed background distribution 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 bruteforce 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 Ω(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 P is the uniform distribution 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 D = U versus from D = U| f must use Ω(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 MAJ-of-AC 0 circuits. We give the argument in Appendix B of the full version of this paper.

Taken together, there is a quartic gap between the (computationally inefficient) upper bound given by Observation 1 and the information-theoretic lower bound of Observation 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 Vol(f ), and (ii) Show that even for the uniform background distribution U over {-1, +1} n , distinguishing whether or not U has been truncated by a degree-d PTF of volume ≈ 1/2 requires Ω(n d/2 ) samples.

We now describe our results in more detail. for which there are two constants 0 < c < C such that everywhere on [a, b] the pdf is between c/(ba) and C/(ba).

An informal statement of our main positive result is below:

Theorem 3 (Efficiently detecting PTF truncation, informal theorem statement). Let 0 < ε < 1. Fix any constant d and any hypercontractive i.i.d. product distribution µ ⊗n over R n . Let f : R n → {0, 1} be an unknown degree-d PTF such that

There is an efficient algorithm that uses Θ(n d/2 /ε 2 ) samples from D and successfully (w.h.p.) distinguishes between the following two cases: (i) D is µ ⊗n , i.e. the "un-truncated" distribution; versus (ii) D is µ ⊗n | f , i.e. µ ⊗n truncated by f .

Note that ε is a lower bound on the probability mass of the distribution µ ⊗n which has been "truncated;" as remarked earlier, without a lower bound on ε, 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 Observation 2) has volume which is not extremely small?

Our main lower bound achieves these goals; it shows that even for the uniform distribution U over {-1, 1} n and for PTFs of volume ≈ 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.

Any algorithm that uses samples from D and successfully (w.h.p.) distinguishes between the cases that (i)

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 P = µ ⊗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 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 D, the algorithm w.h.p.

(i) Outputs "un-truncated" when D = U n ; and (ii) Outputs "truncated" when

To avoid proliferation of parameters, we set ε = 0.1 for the rest of the discussion. We thus have Pr

For any point x ∈ {-1, +1} n , let x ∈ {-1, +1} ( n 1 )+...+( n d ) be the vector given by

In other words, every coordinate of x corresponds to a non-constant monomial in x of (multilinear) degree at most d. Note that the map x → 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) When D = U n , then it is easy to see that E x = 0 (the all-0 vector). This is immediate from the fact that the expectation of any non-constant monomial under U n is 0.

(2) On the other hand, suppose D = U n | f -1 (1) for a degree-d PTF f as above. In this case, it can be shown that

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 E x 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 E x 2 2 up to an additive error of ±c 2 d /2 suffices to distinguish between

Using the idea of "U-statistics" [Hoe94], this suggests a natural unbiased estimator, namely drawing 2T points x (1) , . . . , x (T ) and y (1) , . . . , y (T ) for some T which we will fix later, and then setting

In particular, we have

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

However, in the truncated setting, Var[M] is significantly trickier to analyze; at a high-level, our analysis expresses Var[M] in terms of the "weights" of various levels of the Fourier spectrum of f . 1

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

for the "Fourier weight at level-k", we have

.

, 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

Var

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

Hypercontractive Product Distributions µ ⊗n . We use the same high-level approach (as well as the same estimator M) in order to distinguish low-degree truncation of a hypercontractive product measure µ ⊗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

form a multiplicative group. This group structure is useful because it means that the product of two basis functions is another basis function: For α, β ⊆ [n], we have the product formula

where α △ β denotes the symmetric difference of α and β.

Over an arbitrary hypercontractive measure µ ⊗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 µ ⊗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 1 See Section 2.1 for a formal definition. of orthogonal polynomials (see Section 6.8 of [AAR99]). Lemmas 16 and 17 establish a weak version of a "product formula" between two Fourier basis functions for µ ⊗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 U n to denote the uniform distribution over the n-dimensional Boolean hypercube {-1, +1} n and (χ S ) S for the Fourier basis over {-1, +1} n . To prove Theorem 4, it suffices to construct a distribution F d over degree-d PTFs over {-1, +1} n with the following properties:

(1) The distribution 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 f ∼ F d can be expressed as

The coefficients p(S) will be i.i.d. random variables drawn from the standard Gaussian distribution 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 D 1 and D 2 to proving the following: Suppose u 1 , . . . , 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

for f ∼ F d and where each b i is an independent unbiased random bit. In other words, we aim to show that if the evaluation points u 1 , . . . , u m are randomly chosen (but subsequently known to the algorithm), then f

We establish this last statement by proving something even stronger. Namely, we first observe that the R m -valued random variable (p(u m ), . . . , p(u m )) is an m-dimensional normal random variable for any fixed outcome of u 1 , . . . , u m . Subsequently, we show that this random variable (p(u m ), . . . , p(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.

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 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 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 conditioned 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 [DNS21,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 Ω(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 Section 4 of the full version) 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 P is a background distribution and F is a class of Boolean functions. Under what conditions can we distinguish between D = P versus D = P | f (for some f ∈ F ) with sample complexity asymptotically smaller than the sample complexity of learning F ? We view our results on distinguishing truncation by PTFs as a step towards answering this question.

We write N := {0, 1, . . .} and 1{•} for the 0/1 indicator function. We will write

[n]

Let (R, µ) be a probability space. For n ∈ N, we write L 2 (R n , µ ⊗n ) for the (real) inner-product space of functions f : R n → R with the inner product

Here µ ⊗n denotes the product probability distribution on R n . For q > 0 we write

In particular, for f : R n → {0, 1}, we write Vol(f

We say that a function f : R n → {0, 1} is a degree-d polynomial threshold function (PTF) if there exists a polynomial p : R n → R of degree at most d such that

The primary class of distributions we will consider throughout is that of truncations of an i.i.d. product distribution µ ⊗n by a degreed PTF of at least some minimum volume; more precisely, we will consider the following class of truncations:

where α = α(n) may depend on n (in fact we will be able to take α as small as 2 -Θ( √ 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.

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 (R, µ) is an orthonormal basis B = {χ 0 , χ 1 , . . .} with χ 0 ≡ 1.

It is well known that if L 2 (R, µ) is separable, 2 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 (R n , µ ⊗n ) by taking all possible n-fold products of elements of B; more formally, for a multi-index α ∈ N n , we define

Then the collection B n := χ α : α i ∈ N n forms a Fourier basis for L 2 (R n , µ ⊗n ); this lets us write

We can assume without loss of generality that the basis elements of L 2 (R, µ), namely χ 0 , χ 1 , . . . , are polynomials with deg(χ i ) = i. This is because a polynomial basis can be obtained for L 2 (R, µ) by running the Gram-Schmidt process. By extending this basis to L 2 (R n , µ ⊗n ) by taking products, it follows that we may assume without loss of generality that for a multi-index α ∈ N n , we have

We will also write #α := supp(α) where supp(α) := {i : α i 0}.

Remark 6. While the Fourier coefficients { f (α)} depend on the choice of basis χ α , 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 {χ α } 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 ∈ L 2 (R n , µ ⊗n ), we have

with the latter called Parseval's formula. We also have Plancharel's formula, which says that

2 Recall that a metric space is separable if it contains a countable dense subset.

Table 1: Examples of hypercontractive distributions, along with their accompanying hypercontractivity constants.

Here min(µ) denotes the minimal non-zero probability of any element in the support of the (finitely supported) distribution µ.

Finally, we write

for the Fourier weight of f at level k and the Fourier weight of f up to level k respectively.

The primary analytic tools we will require in both our upper and lower bounds are consequences of hypercontractive estimates for functions in L 2 (R n , µ ⊗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 (R, µ) is hypercontractive if for every q ≥ 2, there is a fixed constant C q (µ) such that for every n ≥ 1 and every multivariate degree-d polynomial p : R n → R we have

where C q (µ) is independent of n and satisfies

for an absolute constant K. When the product distribution µ ⊗n is clear from context, we will sometimes simply write C q := C q (µ) instead.

It is clear from the monotonicity of norms that C q ≥ 1; see Table 1 for examples of hypercontractive distributions with accompanying hypercontractivity constants C q (µ).

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 .

We turn to record several useful consequences of hypercontractivity which will be crucial to the analysis of our estimator as well as to our lower bound. We defer the proofs of Propositions 10 and 11 to the full version of this paper.

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 (R n , µ ⊗n ) is a hypercontractive probability space. Then for any degree-d polynomial p : R n → R with E[p] = 0 and Var[p] = 1, we have

The following proposition bounds Fourier weight up to level k (i.e. W ≤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 (R, µ) is hypercontractive and f : R n → {0, 1} is a Boolean function. Then for all

where K is a constant independent of n.

Remark 12. We note that the Proposition 11 also holds for bounded functions f : R n → [-1, 1] with Vol(f ) := E[| f |], although we will not require this.

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

Theorem 13. Let ε > 0 and let (R, µ) be hypercontractive. There is an algorithm, PTF-Distinguisher (Algorithm 1), with the following performance guarantee: Given access to independent samples from any unknown distribution D ∈ {µ ⊗n } ∪ C PTF (d, 2 - √ n ), the algorithm uses T samples where (1) If D = µ ⊗n , then with probability at least 9/10 the algorithm outputs "un-truncated;"

Output: "Un-truncated" or "truncated" PTF-Distinguisher(D):

(1) Draw 2T independent sample points x (1) , . . . , x (T ) , y (1) , . . . , y (T ) ∼ D, where

(2) Compute the statistic M where

1≤ |α | ≤d and y (j) defined similarly.

(

"un-truncated" otherwise. Before proceeding to the proof of Theorem 13, we give a brief high-level description of Algorithm 1. The algorithm draws 2T independent samples {x (i) , y (i) } i ∈T where T is as above, and then performs a feature expansion to obtain the 2T vectors { x (i) , y (i) } i ∈T where

x (i) := χ α (x (i) )

1≤ |α | ≤d and y (i) is defined similarly. The statistic M employed by the algorithm to distinguish between the un-truncated and truncated is then given by (1) First computing the average of the kernelized x (i) vectors and the kernelized y (i) vectors; and then (2) Taking the inner product between the two averaged kernel vectors.

An easy calculation, given below, relates the statistic 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 anticoncentration of low-degree polynomials to show that the means of the estimators differ by Ω ε (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 {x (i) , y (i) } i ∈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 M ′ given by

x (i) , x (j) 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 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.

The following lemma will be crucial in obtaining a lower-bound for the expectation of our test statistic E[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].

2 for an absolute constant c := c(µ) ∈ (0, 1].

Proof. We may assume that f (x) = 1{p(x) ≥ θ where p : R n → R is a degree-d polynomial with E[p(x)] = p(0 n ) = 0 and ∥p∥ 2 2 = Var[p] = α p(α) 2 = 1. By Cauchy-Schwarz and Plancherel, we get

where we made use of the the fact that p is a degree-d polynomial with p(0 n ) = 0 and Var p(x) = 1. Note that by Proposition 10, we have that either

(5) 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 θ .

Case 1: θ ≥ 1 2 . In this case, we have by Equation (4) that

and so the result follows.

Case 2: 0 ≤ θ < 1 2 . In this case, we have by Proposition 10 that

Once again by Equation (4), we have

where the second inequality follows from f • p being always non-negative and at least 1 2 with probability Pr[p(x) ≥ 1 2 ]. Case 3: θ < 0. Consider the degree-d PTF f † := 1 -f given by

∅ and that Vol(f † ) = 1 -Vol(f ). Repeating the above analysis then gives that

Putting Cases 1 through 3 together, we get that

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

in Equation (5). Suppose that we instead have

Then note that the same trick used in Case 3 by considering f † 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.

Proof. Using Cauchy-Schwarz, we have that

due to the orthonormality of χ α . Using Cauchy-Schwarz once again, we have that

where the final inequality uses hypercontractivity and the fact that χ β (χ γ respectively) is a polynomial of two-norm 1 and degree at

where β, γ ∈ N n .

Proof. We will upper bound the number of pairs (β, γ ) such that |β |, |γ | ≤ d and χ α , χ β χ γ 0; so fix such a pair (β, γ ). We first note that for any i supp(α), we must have β i = γ i ; for otherwise χ α , χ β χ γ = 0 due to orthonormality of χ β i and χ γ i . Also, for each i ∈ supp(α), we must have

by orthonormality and the fact that χ β i • χ γ i is a linear combination of basis functions {χ j } j <α i .

Summing over all i ∈ supp(α), we get that i ∈supp(α )

and so it follows that either i ∈supp(α )

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

completing the proof. □

Proof of Theorem 13. Throughout, we will write

Recalling that there are at most n+k -1

We compute the mean and variance of the estimator M in each case (i.e. when D = µ ⊗n and when D ∈ C PTF (d, 2 - √ n )) separately.

Case 1: D = µ ⊗n . For brevity (and to distinguish the calculations in this case from the following one), we denote the un-truncated distribution by D u := µ ⊗n .

When x (1) , . . . , x (T ) , y (1) , . . . , y (T ) ∼ D u , we have by bi-linearity of the inner product that

as x, y ∼ D u are independent samples and also because of the orthonormality of {χ α }.

Turning to the variance, we have

where x, y ∼ D are independent samples. In this case, we have by our previous calculation (Equation ( 7)) that this is in fact equal to

where we used orthonormality as well as the fact that E D u y • y T = Id m . In this case, f : R n → {0, 1} is a degree-d PTF with

We may assume that f (x) = 1{p(x) ≥ θ } where p : R n → R is a degree-d polynomial with p(0 n ) = 0 and ∥p∥ 2 2 = Var[p] = α p(α) 2 = 1. We have the following easy relation between the Fourier coefficients of f and the means of the characters {χ α } under the truncated distribution D t :

We thus have

where the second line follows from Equation (11) and the final inequality is due to Lemma 15; here c := c(µ) is as in Proposition 10. Turning to the variance of the estimator, we have as before by Equation (9) that

x, y x, y

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

where Equation ( 15) is by the level-k inequalities (Proposition 11) and Equation ( 16) uses the fact that Vol(f ) ≥ 2 - √ n (which is by assumption). Putting everything together, we get that

To summarize, when D = µ ⊗n , we have from Equations ( 7) and ( 10) that

and

For the number of samples being

min 1, ε/(1 -ε), c Θ(d) /(1 -ε)

2 , the correctness of the distinguishing algorithm Algorithm 1 follows directly from Equation (18) and Equations ( 19) and (20) by a simple application of Chebyshev's inequality. □