Cryptographic Hardness of Score Estimation

Authors: min jae song
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 03:06:46

Abstract: We show that L2-accurate score estimation, in the absence of strong assumptions on the data distribution, is computationally hard even when sample complexity is polynomial in the relevant problem parameters. Our reduction builds on the result of Chen et al. (ICLR 2023), who showed that the problem of generating samples from an unknown data distribution reduces to L2-accurate score estimation. Our hard-to-estimate distributions are the "Gaussian pancakes" distributions, originally due to Diakonikolas et al. (FOCS 2017), which have been shown to be computationally indistinguishable from the standard Gaussian under widely believed hardness assumptions from lattice-based cryptography (Bruna et al., STOC 2021; Gupte et al., FOCS 2022).

Main paper: 
 introduction: 
 Diffusion models [70, 72, 42, 73] have firmly established themselves as a powerful approach to generative modeling, serving as the foundation for leading image generation models such as DALL-E 2 [62] , Imagen [66] , and Stable Diffusion [65] . A diffusion model consists of a pair of forward and reverse processes. In the forward process, noise drawn from a standard distribution, such as the standard Gaussian, is sequentially applied to data samples, leading its distribution to a pure noise distribution in the limit. The reverse process, as the name suggests, reverses the noising process and takes the pure noise distribution "backward in time" to the original data distribution, thereby allowing us to generate new samples from the data distribution. A key element in implementing the reverse process is the score function of the data distribution, which is the gradient of its log density. Since the data distribution is typically unknown, the score function must be learned from samples [44, 78, 72] .Recent advances in the theory of diffusion models have revealed that the task of sampling, in fact, reduces to score estimation under minimal assumptions on the data distribution [9, 23, 53, 61, 22, 17, 51, 6] . In particular, Chen et al. [17] have shown that L 2 -accurate score estimates along the forward process are sufficient for efficient sampling. Thus, assuming access to an oracle for L 2 -accurate score estimation, one can efficiently sample from essentially any data distribution. However, this leaves open the question of whether score estimation oracles themselves can be implemented efficiently, in terms of both required sample size and computation, for interesting classes of distributions.We show that L 2 -accurate score estimation, in the absence of strong assumptions on the data distribution, is computationally hard, even when sample complexity is polynomial in the relevant problem parameters. This establishes a statistical-to-computational gap for L 2 -accurate score estimation, which refers to an intrinsic gap between what is statistically achievable and computationally feasible. Our hard-to-estimate distributions are the "Gaussian pancakes" distributions, which previous works [31, 13, 39] have shown are computationally indistinguishable from the standard Gaussian under plausible and widely believed hardness assumptions. In fact, "breaking" the hardness of Gaussian pancakes, by means of an efficient detection or estimation algorithm, has profound implications for lattice-based cryptography, which is central to the post-quantum cryptography standardization led by the National Institute of Standards and Technology (NIST) [58] . Building on the sampling-to-score estimation reduction by Chen et al. [17] , we show that computationally efficient L 2 -accurate score estimation for Gaussian pancakes implies an efficient algorithm for distinguishing Gaussian pancakes from the standard Gaussian. Thus, while sampling may ultimately reduce to L 2 -accurate score estimation under minimal assumptions on the data distribution, score estimation itself requires stronger assumptions on the data distribution for computational feasibility. It is worth noting that the presence of statistical-to-computational gaps in L 2 -accurate score estimation was anticipated by Chen et al. [17, Section 1.1] , who mentioned it without formal statement or proof.Our main result is a simple reduction from the Gaussian pancakes problem (i.e., the problem of distinguishing Gaussian pancakes from the standard Gaussian) to L 2 -accurate score estimation. We show that given oracle access to L 2 -accurate score estimates along the forward process (Assumption A3), one can compute a test statistic that distinguishes, with non-trivial success probability, whether the given score estimates belong to a Gaussian pancakes distribution or the standard Gaussian.A Gaussian pancakes distribution P u with secret direction u ∈ S d-1 can be viewed as a "backdoored" Gaussian. It is distributed as a (noisy) discrete Gaussian along the direction u and as a standard Gaussian in the remaining d -1 directions (see Figure 1 ). 1 A class of Gaussian pancakes (P u ) u∈S d-1 is parameterized by two parameters, γ and σ, which govern the spacing and thickness of pancakes, respectively. For instance, a Gaussian pancakes distribution P u with spacing γ and thickness σ ≈ 0 is essentially supported on the one-dimensional lattice (1/γ)Z along the secret direction u. The Gaussian pancakes problem, then, is a sequence of hypothesis testing problems indexed by the data dimension d ∈ N in which the goal is to distinguish between samples from a Gaussian pancakes distribution (with unknown u) and the standard Gaussian distribution N (0, I d ) with success probability slightly better than random guessing (see Section 2.3 for formal definitions). Thus, our result can be summarized informally as follows. Theorem 1.1 (Informal, see Theorem 3.1). Let γ(d) > 1, σ(d) > 0 be sequences such that σ ≥ 1/poly(d) and the corresponding (γ, σ)-Gaussian pancakes distributions (P u ) u∈S d-1 all satisfy TV(P u , N (0, I d )) > 1/2. Then, there exists a polynomial-time randomized algorithm with access to a score estimation oracle of L 2 -error O(1/ √ log d) that solves the Gaussian pancakes problem.We emphasize that the hardness of estimating score functions of Gaussian pancakes distributions arises solely from hardness of learning. The score function of P u is efficiently approximable by function classes commonly used in practice for generative modeling, such as residual networks [40] . In addition, under the scaling σγ = O(1), which includes the cryptographically hard regime, the secret parameter u can be estimated upto L 2 -error η via brute-force search over S d-1 with poly(d, γ, 1/η) samples (Theorem 4.2). The estimated parameter û in turn enables L 2 -accurate score estimation (see Section 4) . Our estimator, based on projection pursuit [35, 43] , may be of independent interest.We also analyze properties of Gaussian pancakes using Banaszczyk's theorems on the Gaussian mass of lattices [3, 74] . This serves two purposes. Firstly, it allows us to verify that Gaussian pancakes distributions readily satisfy the assumptions for the sampling-to-score estimation reduction of Chen et al. [17] , namely Lipschitzness of the score functions along the forward process (Assumption A1). This is necessary as the proof of our main theorem crucially relies on the reduction. Secondly, Banaszczyk's theorems provide simple means of analyzing properties of Gaussian pancakes, which are interesting mathematical objects in their own right. While these theorems are standard tools in lattice-based cryptography (see e.g., [74, 1] ), they are likely less known outside the community.Theory of diffusion models. Recent advances in the theoretical study of diffusion models have focused on convergence rates of discretized reverse processes [9, 23, 53, 61, 22, 17, 51, 6] . Of particular relevance to our work is the result of Chen et al. [17] who showed that L 2 -accurate score estimates are sufficient to guarantee convergence rates that are polynomial in all the relevant problem parameters under minimal assumptions on the data distribution, namely Lipschitz scores throughout the forward process and finite second moment. Prior studies fell short by requiring strong structural assumptions on the data distribution, such as a log-Sobolev inequality [50, 82] , assuming For fixed γ, the pancakes "blur into each other" as σ increases.L ∞ -accurate score estimates [23] , or providing convergence rates that are exponential in the problem parameters [9, 23, 22] . We note that recent works have made the "minimal" assumptions of Chen et al. [17] even more minimal by considering early stopped reverse processes and dropping the Lipschitz score assumption [15, 6] . We refer to the book draft of Chewi [19] for more background.Gaussian pancakes. The Gaussian pancakes problem stands out among problems exhibiting statistical-to-computational gaps due to its versatility and strong hardness guarantees. Initially introduced as hard-to-learn Gaussian mixtures in the work of Diakonikolas et al. [31] , which established their SQ hardness, Gaussian pancakes have been extensively utilized in establishing SQ lower bounds for various statistical inference problems such as robust Gaussian mean estimation [31] and agnostically learning halfspaces and ReLUs over Gaussian inputs [28] . For further details, we refer to the textbook by Diakonikolas and Kane [29, Chapter 8] . Gaussian pancakes distributions themselves serve as instances of fundamental high-dimensional inference problems such as non-Gaussian component analysis [8] and Wasserstein distance estimation in the spiked transport model [57] .Bruna et al. [13] initiated the exploration of the cryptographic hardness of Gaussian pancakes. They showed that assuming hardness of worst-case lattice problems, fundamental to lattice-based cryptography [56, 60] , both the Gaussian pancakes and the closely related continuous learning with errors (CLWE) problems are hard. Follow-up work by Gupte et al. [39] showed that the learning with errors (LWE) problem [63] , a versatile problem which lies at the heart of numerous lattice-based cryptographic constructions, reduces to the Gaussian pancakes as well. These cryptographic hardness results have sparked a wave of recent works showcasing various applications of this newly discovered property of Gaussian pancakes. Notable examples include planting undetectable backdoors in machine learning models [38] , novel public-key encryption schemes based on Gaussian pancakes [10] , and cryptographic hardness of agnostically learning halfspaces [26, 75] .For additional related work on score estimation and statistical-to-computational gaps, see Section A.Our work brings together the latest advances from the theory of diffusion models and computational complexity of statistical inference. This intersection provides fertile ground for future research, some avenues of which we outline below.Stronger data assumptions for efficient score estimation. Our result shows that for any class of distributions that encompasses hard Gaussian pancakes, computationally efficient L2 -accurate score estimation is impossible. This implies that stronger assumptions on the data, which exclude Gaussian pancakes, are necessary for efficient score estimation. Finding assumptions that exclude hard instances while being able to capture realistic models of data is an interesting open problem.Weaker criteria for evaluating sample quality. In the context of learning Gaussian pancakes, if the goal of the sampling algorithm were to merely fool computationally bounded testers that lack knowledge of the secret u ∈ S d-1 , then it could simply generate standard Gaussian samples and fool any polynomial-time test. Thus, sampling is strictly easier than L 2 -accurate score estimation if the criteria for evaluating sample quality is less stringent. This suggests exploring sampling under different evaluation criteria, such as "discriminators" with bounded compute or memory. For example, Christ et al. [20] have used weaker notions of sample quality in the context of watermarking large language models (LLMs). More precisely, they used the notion of computational indistinguishability to guarantee quality of the watermarked model relative to the original model. Exploring potential connections to the literature on leakage simulation [45, 18, 76] and outcome indistinguishability [41, 32, 33] is also an interesting future direction, as these areas have addressed related questions for distributions on finite sets.Extracting "knowledge" from sampling algorithms. A key difficulty in directly reducing the Gaussian pancakes problem to sampling is that the Gaussian pancakes problem is hard for polynomialtime distinguishers, even with access to exact sampling oracles (see Section 2.3 for more details). 2 Thus, any procedure utilizing the learned sampler in a black box manner cannot solve the Gaussian pancakes problem. This is puzzling since for the algorithm to have "learned" to generate samples from the given distribution, it ought to possess some non-trivial information about it (e.g., leak information about the secret parameter u)! This raises the question: How much "knowledge" can we extract with white box access to the sampling algorithm? Under reasonable structural assumptions on the sampling algorithm, can we extract privileged information about the data distribution it simulates, beyond what is obtainable solely via sample access? Our work provides one such example. White box access to a diffusion model gives access to its score estimates. These score estimates, which enable efficient solutions to the Gaussian pancakes problem, constitute privileged knowledge that cannot be learned efficiently even with unlimited access to bona fide samples. 
preliminaries: 
 Notation. We denote by (a t ) the sequence a 1 , a 2 , a 3 , . . . indexed by t ∈ N. When there is no natural ordering on the index set (e.g., (a u ) u∈S d-1 ), we interpret it as a set. We write a ≲ b or a = O(b) to mean that a ≤ Cb for some universal constant C > 0. The notation a ≳ b and a = Ω(b) are defined analogously. We write a ≍ b or a = Θ(b) to mean that a ≲ b and a ≳ both hold. We write ∧, ∨ to mean logical AND and OR, respectively. We also write a ∧ b and a ∨ b to mean min(a, b) and max(a, b), respectively. We denote by Q d the "standard" Gaussian N (0, 1/(2π)I d ) (see Remark 2.3). We omit the subscript d when it is clear from context.We give a brief exposition on denoising diffusion probabilistic models (DDPM) [42] , a specific type of diffusion model, since the main reduction of Chen et al. [17] pertains to DDPMs. This section closely follows [17, Section 2.1] and [80, Section 3] Let D be the target distribution defined on R d . In DDPMs, we begin with the forward process, an Ornstein-Uhlenbeck (OU) process that converges towards Q = N (0, (1/2π)I d ), which is described by the following stochastic differential equation (SDE). Note that the constant 1/ √ π in front of dW t in Eq.( 1) is non-standard. 3 See Remark 2.3 for an explanation of our unconventional choice of variance for the resulting stationary distribution Q.EQUATIONwhere W t is the standard Brownian motion in R d .Let D t be the distribution of X t along the OU process. It is well-known that for any distribution D, D t → Q exponentially fast in various divergences and metrics such as the KL divergence [2] . In this work, we only consider Gaussian pancakes (P u ) and the standard Gaussian Q. If D = P u and t > 0, then the distribution D t is simply another Gaussian pancakes distribution with a larger thickness parameter (see Definition 2.5). Meanwhile, if D = Q, then D t = Q for any t ≥ 0. We run the OU process until time T > 0, and then simulate the reverse process, described by the following SDE.EQUATIONHere, ∇ log D t is called the score function of D t . Since the target D is not known, in order to implement the reverse process the score function must be estimated from data samples. Assuming for the moment that we have exact scores (∇ log D t ) t∈[0,T ] , if we start the reverse process from F 0 = D T , we have Y t ∼ F t = D T -t for any 0 ≤ t ≤ T , and ultimately Y T ∼ F T = D. Thus, starting from (approximately) pure noise D T ≈ Q, the reverse process generates fresh samples from the target distribution D. We need to make several approximations to algorithmically implement this reverse process. In particular, we need to approximate D T by Q, discretize the continuous-time SDE, and approximate scores along the (discretized) forward process. Let h > 0 be the step size for the SDE discretization and denote N := T /h. Given score estimates (s kh ) k∈[N ] , the DDPM algorithm performs the following update (see e.g., [67, Chapter 4.3] ).EQUATIONwhere z k ∼ Q is an independent Gaussian vector. Note that the only dependence of the reverse process on the target distribution D arises through the score estimates(s kh ) k∈[N ] .The result of Chen et al. [17] demonstrates polynomial convergence rates of this process to the target distribution D, assuming access to L 2 -accurate score estimates (s kh ) k∈[N ] and minimal conditions on the target D. We refer to Section 3.1 for a formal statement of their assumptions and theorem. The dual lattice of a lattice L, denoted by L * , is defined asL * = {y ∈ R d | ⟨x, y⟩ ∈ Z for all x ∈ L} . If B is a basis of L then (B T ) -1 is a basis of L * ; in particular, det(L * ) = det(L) -1 .Fourier analysis. We define the Fourier transform of a function f : R d → C byf (y) = R d f (x) exp(-2πi⟨x, y⟩)dx .The Poisson summation formula offers a valuable tool for analyzing functions defined on lattices. f (L) = det(L * ) • f (L * ) ,where we denote f (S) = x∈S f (x) for any set S.Discrete Gaussians. A discrete Gaussian is a discrete distribution whose probability mass function is given by the Gaussian function. These distributions are closely related to Gaussian pancakes distributions and their properties will be crucial for our analysis. Definition 2.2 (Gaussian function). We define the Gaussian function ρ s : R d → R of width s > 0 by ρ s (x) := exp(-π∥x∥ 2 /s 2 ) .When s = 1, we omit the subscript and simply write ρ. In addition, for any lattice L ⊂ R d , we denote by ρ s (L) = x∈L ρ s (x) the corresponding Gaussian mass of L.Remark 2.3 (Non-standard choice of "standard" variance). We refer to Q d = N (0, 1/(2π)I d ) as the "standard" Gaussian. This is indeed the standard choice in lattice-based cryptography because it simplifies normalization factors that arise from taking Fourier transforms. For instance, it allows us to simply write ρ s = s n ρ 1/s and ρ = ρ for s = 1. To translate these results for the "usual" standard Gaussian, we can simply replace s with s/ √ 2π for each occurrence.Definition 2.4 (Discrete Gaussian). For any lattice L ⊂ R d , parameter s > 0, and shift t ∈ R d , the discrete Gaussian D L-t,s is a distribution supported on the coset L -t with probability massD L-t,s (x) = ρ s (x -t) ρ s (L -t) .We denote by A γ the discrete Gaussian of width s = 1 supported on the one-dimensional lattice (1/γ)Z. The distribution of a Gaussian pancakes distribution P u along the hidden direction is a smoothed discrete Gaussian, which we formalize in the following. Definition 2.5 (Smoothed discrete Gaussian). For any γ > 0, let A γ be the discrete Gaussian of width 1 on the lattice (1/γ)Z. We define the σ-smoothed discrete Gaussian A σ γ as the distribution of the random variable y induced by the following process.y = 1 √ 1 + σ 2 (x + σz) , where x ∼ A γ and z ∼ Q .Furthermore, the density of A σ γ is given byEQUATION)Likelihood ratio of smoothed discrete Gaussians. Let A σ γ be the σ-smoothed discrete Gaussian on (1/γ)Z. Its likelihood ratio T σ γ with respect to the standard Gaussian is given byEQUATIONWhen γ and σ are clear from context, we omit them and simply denote the likelihood ratio by T .We define Gaussian pancakes distributions using the likelihood ratio T σ γ = A σ γ /Q. It is important to note that our parametrization differs from the one used in previous works [13, 39] . We believe our parametrization is more convenient as it elucidates a natural partial ordering on the space of parameters (γ, σ). In addition, there is an explicit mapping between the two different parametrizations, so computationally hard parameter regimes identified by previous works [13, 39] can readily be translated into setting. See Remark 2.7 for more details. Definition 2.6 (Gaussian pancakes). For any d ∈ N, spacing and thickness parameters γ, σ > 0, we define the (γ, σ)-Gaussian pancakes distribution P σ γ,u with secret direction u ∈ S d-1 byP σ γ,u (x) := Q(x) • T σ γ (⟨x, u⟩) , where Q = N (0, (1/2π)I d ) and T σγ is the likelihood ratio of A σ γ with respect to Q. When parameters γ, σ are clear from context, we omit them in the notation and simply denote the distribution by P u to avoid clutter. A σ γ arises in the OU process for the discrete Gaussian A γ at time t = log √ 1 + σ 2 . Consequently, for any fixed γ > 0, there exists a natural partial ordering on the family of Gaussian pancakes parametrized by (γ, σ), given by (γ, σ 1 ) ≤ (γ, σ 2 ) whenever σ 1 ≤ σ 2 . This ordering arises from the fact that A σ1 γ reduces to A σ2 γ whenever σ 1 ≤ σ 2 via the OU process starting at t 1 = log 1 + σ 2 1 and run until t 2 = log 1 + σ 2 2 . Definition 2.8 (Advantage). Let A : X → {0, 1} be any decision rule (i.e., distinguisher). For any pair of distributions (P, Q) on X , we define the advantage of A byα(A) := P[A(X) = 1] -Q[A(X) = 1] .For a sequence of decision rules (A d ) d∈N and distribution pairs(P d , Q d ) d∈N , we say (A d ) has non-negligible advantage with respect to (P d , Q d ) if its advantage sequence α d = α(A d ) is a non-negligible function in d, i.e., a function in Ω(d -c) for some constant c > 0. Definition 2.9 (Computational indistinguishability). A sequence of distribution pairs (P d , Q d ) is computationally indistinguishable if no poly(d)-time computable decision rule achieves nonnegligible advantage. Definition 2.10 (Gaussian pancakes problem). For any sequences γ(d), σ(d) > 0 and n(d) ∈ N, the (γ, σ, n)-Gaussian pancakes problem is to distinguish (P d , Q d ) with non-negligible advantage, where P d is the n-sample distribution induced by the following two-stage process: 1) draw u uniformly from S d-1 , 2) draw n i.i.d. Gaussian pancakes samples x 1 , . . . , x n ∼ P ⊗n u , andQ d = Q ⊗n d , i.e., the distribution of n i.i.d. standard Gaussian vectors.As will be explained next, the exact number of samples n is irrelevant for most applications due to the cryptographic hardness of the Gaussian pancakes problem. For certain parameter regimes of (γ, σ), the problem maintains its computational intractability regardless of the sample size n.There is an abundance of evidence demonstrating the hardness of the Gaussian pancakes problem. This makes it compelling to directly assume that Gaussian pancakes and the standard Gaussian are computationally indistinguishable (see Definition 2.9) for certain parameter regimes of (γ, σ). Initial results by Bruna et al. [13, Corallary 4.2] showed that the Gaussian pancakes problem is as hard as worst-case lattice problems for any parameter sequence (γ, σ) satisfying γ ≥ 2 √ d and σ ≥ 1/poly(d). SQ hardness of the problem has been demonstrated as well [31, 13, 27] . Perhaps surprisingly, the reduction of Bruna et al. shows that even with unlimited access to an exact sampling oracle, no polynomial-time algorithm A can achieve non-negligible advantage on the (γ, σ)-Gaussian pancakes problem. This stems from the fact that the running time of A naturally restricts the number of samples it can "see", resolving the apparent mystery.An important follow-up work by Gupte et al. [39] reduced the well-known LWE problem to the Gaussian pancakes problem. Assuming sub-exponential hardness of LWE [52] , a standard assumption underlying post-quantum cryptosystems expected to be standardized by NIST, the Gaussian pancakes problem is hard for any γ ≥ (log d) 1+ε , where ε > 0 is any constant, and σ ≥ 1/poly(d) [39, Section 1.2]. Taken together, these findings strongly support the hardness of Gaussian pancakes for the specified regimes of (γ, σ). Note, however, that the condition σ ≥ 1/poly(d) is necessary for hardness as there exist polynomial-time algorithms, based on lattice basis reduction, for exponentially small σ [83, 25] . 
hardness of score estimation: 
 Our main result is Theorem 3.1, which presents a reduction from the Gaussian pancakes problem to L 2 -accurate score estimation. Since the Gaussian pancakes problem exhibits both cryptographic and SQ hardness in the parameter regime γ ≥ 2 √ d and σ ≥ 1/poly(d) [13, 39] , these notions of hardness extend to the task of estimating scores of Gaussian pancakes. Further details on the hardness of the Gaussian pancakes problem can be found in Section 2.3. Theorem 3.1 (Main result). Let γ(d) > 1, σ(d) > 0 be any pair of sequences such that σ ≥ 1/poly(d) and the corresponding (sequence of) (γ, σ)-Gaussian pancakes distributions (P u ) u∈S d-1satisfies TV(P u , Q d ) > 1/2 for any d ∈ N. Then, for any δ ∈ (0, 1), there exists a poly(d)•log(1/δ)time algorithm with access to a score estimation oracle of L 2 -error O(1/ √ log d) that solves the (γ, σ)-Gaussian pancakes problem with probability at least 1 -δ.The requirement TV(P u , Q d ) > 1/2 is mild and entirely captures interesting parameter regimes of (γ, σ) for which cryptographic and SQ hardness of Gaussian pancakes are known. We provide a sufficient condition in Lemma B.9, which shows that γσ < C for some constant C > 0 ensures separation in TV distance. Theorem 3.1 implies that even a score estimation oracle running in time poly(d, 2 1/ε 2 ), where ε > 0 is the L 2 estimation error bound, implies a poly(d) time algorithm for the Gaussian pancakes problem. This means that estimating the score functions of Gaussian pancakes to L 2 -accuracy ε even in poly(d, 2 1/ε 2 ) time is impossible under standard cryptographic assumptions.Here, we sketch the proof of Theorem 3.1 and defer full details to Section B.1. We first recall the sampling-to-score estimation reduction of Chen et al. [17] and its required assumptions to illustrate the main idea behind our reduction. The precise formulation of our idea is given in Lemma 3.3.Assumptions on data distribution. The reduction of Chen et al. [17] requires the following assumptions on the data distribution D over R d . A1 (Lipschitz score). For all t ≥ 0, the score ∇ log D t is L-Lipschitz. A2 (Finite second moment). D has finite second moment, i.e., m 2 2 := E x∼D [∥x∥ 2 ] < ∞. A3 (Score estimation error). For step size h := T /N and all k = 1, . . . , N , Theorem 2] ). Suppose assumptions A1-A3 hold. Let Q d be the standard Gaussian on R d and let F T be the output of the DDPM algorithm (Section 2.1) at time T with step size h := T /N such that h ≲ 1/L, where L ≥ 1. Then, it holds thatE D kh [∥s kh -∇ log D kh ∥ 2 ] ≤ ε 2 score . Theorem 3.2 ([17,EQUATIONIn particular, ifm 2 ≤ d, then T ≍ max(log(KL(D ∥ Q d )/ε), 1) and h ≍ ε 2 /(L 2 d) gives TV(F T , D) ≲ ε + ε score • max( log(KL(D ∥ Q d )/ε), 1) , for N = Θ L 2 d ε 2 .Theorem 3.2 shows that if the unknown data distribution D has Lipschitz scores and satisfies m 2 ≤ d, then its ε-accurate score estimates along the discretized forward process (s kh ) k∈[N ] can be used to compute a certificate of Gaussianity defined as follows.EQUATION)Using ∆ as a test statistic, we decide D ∈ (P u ) u∈S d-1 if ∆ ≥ τ for some carefully chosen threshold τ > 0 and D = Q d otherwise. This test statistic is motivated by the observation that the discretized reverse process depends on the data distribution D solely through its score estimates (see Eq.( 3)).For any sequence of score estimates (s t ) t∈[0,T ] the reverse process outputs F T that is TV-close to D provided its L 2 error along the forward process (D t ) t∈[0,T ] is small.We claim that if ∆ ≤ η 2 and the score estimates (s kh ) are ε-accurate for (D kh ), then the output of the reverse process F T is roughly (ε + η)-close in TV distance to the standard Gaussian. This is because the standard Gaussian is invariant throughout the OU process, so ∆ is, in fact, the L 2 score estimation error bound for the case where the data distribution D is equal to Q d . In other words, ∆ ≤ η 2 means that for all k ∈ [N ], the score estimates (s kh ) are η-close to -2πx which is the score function of Q d . Thus, ∆ is small only if D is close in TV distance to Q d , which shows that ∆ distinguishes between D = Q d and D ∈ (P u ) u∈S d-1 provided TV(P u , Q d ) > 1/2.∆ = max k∈[N ] E Q d ∥s kh (x) + 2πx∥ 2 , then TV(D, Q d ) ≲ ε + ∆ log(K/ε) .In particular, if TV(D, Q d ) > 1/2 then there exist constants C 1 , C 2 > 0 such that for any score estimates (s kh ) k∈[N ] of the forward process satisfying max k∈[N ] E D kh ∥s kh (x)-∇ log D kh (x)∥ 2 ≤ C 1 / log K, it holds ∆ ≥ C 2 / log K .Proof. By Theorem 3.2 and our choice of L 2 score estimation error bound ε, we have TV(F T , D) ≤ ε. In addition, the score estimates (s t ) also satisfy a √ ∆-error bound with respect to the forward process of Q d , which is invariant with respect to time t. Thus, Theorem 3.2 applied with D = Q d as the data distribution, discretization parameters T, h, and score estimates (s kh ) gives TV(F T , Q d ) ≲∆ log(K/ε). By the triangle inequality, we haveTV(D, Q) ≤ TV(F T , D) + TV(F T , Q) ≲ ε + ∆ log(K/ε) .The second part of the theorem follows from using the assumptions TV(D, Q) > 1/2, K ≥ 2, and fixing ε > 0 to a sufficiently small constant, which gives us 1 ≲ ∆ log K . 
sample complexity of gaussian pancakes: 
 To establish that there is indeed a gap between statistical and computational feasibility, we demonstrate a polynomial upper bound on the sample complexity of L 2 -accurate score estimation for Gaussian pancakes. In particular, we show that a sufficiently good estimate û of the hidden direction u is enough (Lemma 4.1). The polynomial sample complexity of score estimation then follows from Theorem 4.2, which shows that if γ(d) and σ(d) satisfy γσ = O(1), then 1 -⟨ û, u⟩ 2 ≤ η 2 is statistically achievable with poly(d, γ, 1/η) samples, albeit through brute-force search over S d-1 .Our estimator û is based on projection pursuit [35, 43] . We design a functional E : S d-1 → R of the form E(v) := E x∼Pu g(⟨x, v⟩) with g : R → R carefully chosen to ensure that E(v 1 ) ≥ E(v 2 ) if and only if |⟨v 1 , u⟩| ≥ |⟨v 2 , u⟩|. Given such a "monotonic" functional (its empirical counterpart Ê, to be precise), our estimator for the secret direction u is essentially û = arg maxv∈S d-1 Ê(v) .We remark that parameter regime γσ = O(1) in Theorem 4.2 encompasses the cryptographically hard regime of Gaussian pancakes. It is also worth noting that if min(γ, γσ) = ω( √ log d), then Gaussian pancakes are statistically indistinguishable from Q d by Lemma B.10.We defer the full proofs of Lemma 4.1 and Theorem 4.2 to Section C. Lemma 4.1 (Score-to-parameter estimation reduction). For any γ > 1, σ > 0, let P u be the (γ, σ)-Gaussian pancakes distribution with secret direction u ∈ S d-1 . Given any η ∈ (0, 1) and û∈ S d-1 such that 1 -⟨ û, u⟩ 2 ≤ η 2 , the score estimate ŝ(x) = -2πx + ∇ log T σ γ (⟨x, û⟩) satisfies E x∼Pu ∥ŝ(x) -s(x)∥ 2 ≲ max(1, 1/σ 8 ) • η 2 d , where s(x) = -2πx + ∇ log T σ γ (⟨x, u⟩)is the true score function of P u . Theorem 4.2 (Sample complexity of parameter estimation). For any constant C > 0, given γ(d) > 1, σ(d) > 0 such that γσ < C, estimation error parameter η > 0, and δ ∈ (0, 1), there exists a bruteforce search estimator û : R d×n → S d-1 that uses n = poly(d, γ, 1/η, 1/δ) samples and achieves ∥ û(x 1 , . . . , x n ) -u∥ 2 ≤ η 2 with probability at least 1 -δ over i.i.d. samples x 1 , . . . , x n ∼ P u , where P u is the (γ, σ)-Gaussian pancakes distribution with secret direction u ∈ S d-1 . Score estimation. Several works have addressed the statistical question of sample complexity for various data distributions and function classes used to estimate the score [16, 55, 80] . Wibisono et al. [80] study score estimation for the class of subgaussian distributions with Lipschitz scores. By establishing a minimax lower bound exhibiting a curse of dimensionality, they show that the exponential dependence on dimension is fundamental to this nonparametric distribution class, underscoring the need for stronger assumptions on the data distribution for polynomial sample complexity. Chen et al. [16] study neural network-based score estimation and derive finite-sample bounds for data distributions that lie on a low-dimensional linear subspace, which circumvents the curse of dimensionality. Mei and Wu [55] study neural network-based score estimation for graphical models which are intrinsically high dimensional. Assuming the efficiency of variational inference approximation to the data-generating graphical model, they show that the score function can be efficiently approximated by residual networks [40] and learned with polynomially many samples. Efficient score estimation both in sample and computational complexity has been achieved by Shah et al. [68] for mixtures of two spherical Gaussians using a shallow neural network architecture that matches the closed-form expression of the score function.Statistical-to-computational gaps. Statistical-to-computational gaps have a rich history in statistics, machine learning, and computer science [7, 85, 54, 69, 24] . Indeed, many high-dimensional inference problems exhibit gaps between what is achievable statistically (with infinite computational resources) and what is achievable under limited computation. Notable examples include sparse PCA [7] , sparse linear regression [85, 79] , and learning one-hidden-layer neural networks over Gaussian inputs [37, 30] .Since there are no known reductions from NP-hard problems, the gold standard for computational hardness, to any average-case problem arising in statistical inference, alternative techniques have been developed to provide rigorous evidence of hardness. These include proving lower bounds for restricted classes of algorithms like sum of squares (SoS) [49, 59, 5] and statistical query (SQ) algorithms [46, 34] , which capture spectral, moment, and tensor methods, and reducing from "canonical" problems believed to be hard on average, such as the planted clique [11] or random k-SAT [21] problem. We refer the reader to surveys and monographs [84, 4, 81, 36, 48, 47, 29] for a thorough overview of recent literature and diverse perspectives ranging from computer science and information theory to statistical physics. (P u , Q) > 1/2, Lemma 3.3 implies that if D ∈ (P u ) u∈S d-1 , there exist universal constants C 1 , C 2 > 0 such that if the score estimates (s kh ) k∈[N ] satisfy E D kh ∥s kh (x) -∇ log D kh (x)∥ 2 ≤ C 1 / log d, then ∆ ≥ C 2 / log d.Let τ = C 2 / log d and η 2 = min(τ /4, C 1 / log d). Then, we have that with η-accurate score estimates (s kh ), we have ∆ ≤ η 2 ≤ τ /4 if D = Q and ∆ ≥ τ otherwise. Note that η ≍ 1/ √ log d and N = T /h ≍ L 2 d log K ≤ poly(d). Our proposed distinguisher A uses a finite-sample estimate of ∆ as a test statistic (Eq.( 7)) using η-accurate score estimates (s kh ) k∈[N ] and N ℓ i.i.d. standard Gaussian samples (z(k) i ) (k,i)∈[N ]×[ℓ]as follows. Later, it will be shown that setting the batch size ℓ to ℓ = poly(d) is sufficient for our distinguisher A.∆ = max k∈[N ] ∆(k) , where ∆(k) = 1 ℓ ℓ i=1 s kh (z (k) i ) + 2πz (k) i 2 .The distinguisher A decides D = Q if ∆ ≤ τ /E Dt ∥s t (x) -∇ log D t (x)∥ 2 = E Dt ∥s t (x) -∇ log D t (x)∥ 2 • 1[∥st(x)∥ ≤ M ] + E Dt ∥∇ log D t (x)∥ 2 • 1[∥st(x)∥ > M ] .The second term on the RHS can be upper bounded byEQUATIONwhere in Eq.( 8) we used the fact that if ∥s t (x)∥ > M and ∥∇ logD t (x)∥ ≤ M/2, then ∥∇ log D t (x)∥ ≤ M/2 ≤ ∥s t (x) -∇ log D t (x)∥.Putting things together, we haveE Dt ∥s t (x) -∇ log D t (x)∥ 2 ≤ E Dt ∥s t (x) -∇ log D t (x)∥ 2 + E Dt ∥∇ log D t (x)∥ 2 • 1[∥∇ log D t (x)∥ > M/2] . It remains to bound E[∥∇ log D t (x)∥ 2 • 1[∥∇ log D t (x)∥ > M/2]] which depends only on the distribution D t . We choose M ≍ ( √ d + 1/σ 2 ). If D = Q d , then D t = Q d forE Q d ∥x∥ 2 • 1[∥x∥ > M/2] ≤ E Q d ∥x∥ 4 • Pr Q d [∥x∥ > M/2] ≤ exp(-CM 2 ) .On the other hand, if D = P u , then by Lemma B.4, Eq.( 13) and the triangle inequality∥∇ log P u (x)∥ = x + (T σ γ ) ′ (⟨x, u⟩) T σ γ (⟨x, u⟩) u ≤ ∥x∥ + 8π(1 + 1/σ 2 ) .Using a similar concentration argument, we haveEQUATIONThe OU process applied to P u only increases the σ parameter, so the upper bound in Eq.( 9) holds uniformly over the forward process (D kh ) k∈[N ] if D = P u . Thus, choosing M ≍ ( √ d + 1/σ 2 ) = poly(d) as the truncation threshold suffices to ensure that for all discretized time steps t = kh, the L 2 score estimation error with respect to the forward process (D t ) introduced by truncating the score estimate s t to st is negligible in d. Therefore, we apply Lemma Lemma B.2 (Second moment of Gaussian pancakes). For any γ, σ > 0, and u ∈ S d-1 , the (γ, σ)-Gaussian pancakes P u satisfiesE x∼Pu [∥x∥ 2 ] ≤ d 2π .Proof. Without loss of generality, we assume u = e 1 . Then,E x∼Pu ∥x∥ 2 = E x∼A σ γ [x 2 ] + (d -1)E z∼Q z 2 = E x∼A σ γ [x 2 ] + d -1 2π .In addition,E x∼A σ γ [x 2 ] = E x∼Aγ E z∼N (0,1/(2π)) x/ 1 + σ 2 + σz/ 1 + σ 2 2 = 1 1 + σ 2 • E x∼Aγ [x 2 ] + σ 2 1 + σ 2 • 1 2π.Thus, it suffices to establish an upper bound on E x∼Aγ x 2 , i.e., the second moment of the discrete Gaussian on (1/γ)Z. Using the Poisson summation formula (Lemma 2.1) and the fact that the Fourier transform ofEQUATION< 1 2πwhere in Eq.( 10), we used the fact that ρ(γZ) = ρ((1/γ)Z)/γ and that the second term is positive.Since E x∼A σ γ [x 2 ] is a convex combination of E x∼Aγ [x 2] and 1/(2π), the conclusion follows.In this section, we show that score functions of Gaussian pancakes distributions are Lipschitz with respect to x ∈ R d . The score function of P u , the (γ, σ)-Gaussian pancakes distribution with secret direction u ∈ S d-1 , admits the following analytical expression.EQUATION)We use Banaszczyk's theorems on the Gaussian mass of lattices [3] to upper bound the Lipschitz constant of (T σ γ ) ′ /T σ γ in terms of σ. ∈ R d , exp(-π • dist(t, L) 2 /s 2 ) • ρ s (L) ≤ ρ s (L -t) ≤ ρ s (L) . Lemma B.5 (Lipschitzness of ∇ log P u ). For any γ > 1, σ > 0, s = σ/ √ 1 + σ 2, and u ∈ S d-1 , the score function of the (γ, σ)-Gaussian pancakes distribution P u satisfies the Lipschitz condition:EQUATIONand the likelihood ratio T σ γ of the σ-smoothed discrete Gaussian A σ γ relative to N (0, 1/(2π)) satisfies the uniform bound:EQUATION)Proof. It suffices to analyze the Lipschitz constant of the univariate function (T σ γ ) ′ /T σ γ : R → R, which we denote by f = (T σ γ ) ′ /T σ γ since for any x ̸ = y ∈ R d ,∥∇ log P u (y) -∇ log P u (x)∥ ≤ 2π∥y -x∥ + (f (⟨y, u⟩) -f (⟨x, u⟩))u ≤ 2π∥y -x∥ + |f (⟨y, u⟩) -f (⟨x, u⟩)| |⟨y, u⟩ -⟨x, u⟩| • |⟨y -x, u⟩| ≤ 2π + sup a,b∈R f (b) -f (a) b -a ∥y -x∥ .We bound the Lipschitz constant of the function f (z) by demonstrating a uniform upper bound on the absolute value of its derivative f ′ (z) := (d/dz)f (z). For notational convenience, we omit the parameters γ, σ when denoting the likelihood ratio T . The derivative f ′ is given byEQUATION) Hence, |f ′ (z)| ≤ |(T ′′ /T )(z)| + |(T ′ /T )(z)| 2 for any z ∈ R.We prove uniform upper bounds on the two RHS terms, starting with |T ′ /T |. Using the definition of the likelihood ratio T (Eq.( 5)), we haveEQUATIONwhere z = z/ √ 1 + σ 2 , s = σ/ √ 1 + σ 2 , L = (1/γ)Z, and D L-z,s is the discrete Gaussian distribution of width s on the lattice coset L -z.We upper bound E[|x|] via a tail bound on D L-z,s . Let r > 0 be any number and denote t := r/s -1/(2π). By Theorem B.3 and Lemma B.4,ρ s ((L -z) \ rB 2 ) < exp(-πt 2 )ρ s (L) < exp(-πt 2 ) exp(π • dist(z, L) 2 /s 2 )ρ s (L -z) = exp(-π((r/s -1/(2π)) 2 -1/(2sγ) 2 ))ρ s (L -z) ,where we used the fact that dist(z, L) ≤ 1/(2γ) for any z ∈ R in the last line.Thus, for r/(2s) ≥ 1/(2π) + 1/(2sγ),EQUATION)Denote r 0 := s 2/π + 1/γ. Note that r 0 < 2/π + 1/γ since s ∈ [0, 1). Then,EQUATIONTherefore by Eq.( 15) and ( 17), for any z ∈ REQUATION)Eq.( 13) in the statement of Lemma B.5 follows immediately from the fact that s < min(1, σ) and γ > 1. Next, we demonstrate a uniform upper bound on T ′′ /T . The analytical expression of T ′′ /T is given byT ′′ (z) T (z) = 2π σ 2 2 • k∈Z (z - √ 1 + σ 2 k/γ) 2 ρ σ (z - √ 1 + σ 2 k/γ) k∈Z ρ σ (z - √ 1 + σ 2 k/γ) - σ 2 2π = 2π σs 2 E x∼D L-z,s x 2 - s 2 2π,where z = z/ √ 1 + σ 2 , s = σ/ √ 1 + σ 2 , and L = (1/γ)Z.To uniformly bound |T ′′ /T |, we upper bound the second moment of D L-z,s . Again, let r 0 = s 2/π + 1/γ. Using the tail bound from Eq.( 16) and the fact thatEQUATION)Applying Eq.( 17) and Eq.( 19) to the expression for f ′ = T ′ /T (Eq.( 14)) and using the fact that γ > 1 and s = σ/ √ 1 + σ 2 ≤ min(1, σ), we have∥f ′ ∥ ∞ ≤ ∥T ′′ /T ∥ ∞ + ∥(T ′ /T ) 2 ∥ ∞ ≤ 2π σs 2 (1 + 1/2π)s 2 + 1/γ 2 + ((2 + 2/π)s + 1/γ) 2 ≤ 100π 2 s 4 .Therefore,∇ log P u (x) is O(1/s 4 )-Lipschitz since 2π + ∥f ′ ∥ ∞ ≲ 1/s 4 .We now prove lower (Lemma B.9) and upper (Lemma B.10) bounds on the TV distance between Gaussian pancakes distributions (P u ) and the standard Gaussian Q. We also show that the KL divergence is upper bounded by poly(d) for Gaussian pancakes with σ ≥ 1/poly(d) (Lemma B.11).The following fact reduces the d-dimensional problem of bounding TV(P u , Q d ) to a one-dimensional problem of bounding TV(A σ γ , Q), where A σ γ is the σ-smoothed discrete Gaussian on (1/γ)Z and Q = Q 1 . Without loss of generality, assume u = e 1 . Then, by the L 1 -characterization of the TV distance, we haveTV(P u , Q d ) = 1 2 |P u (x) -Q d (x)|dx = 1 2 Q d (x)|T σ γ (x 1 ) -1|dx = 1 2 |A σ γ (x 1 ) -Q(x 1 )|dx 1 = TV(A σ γ , Q) .Hence, it suffices to demonstrate bounds on TV(A σ γ , Q). The same applies to the KL divergence sinceKL(P u ∥ Q d ) = KL(A σ γ ∥ Q).We first demonstrate a lower bound on the total variation distance. To this end, we introduce the periodic Gaussian distribution and its useful properties. The key lemma is Lemma B.9.For any one-dimensional lattice L ⊂ R, we define the periodic Gaussian distribution Ψ L,s : R → R ≥0 as follows.Ψ L,s (z) := 1 s x∈L ρ s (x -z) = ρ s (L -z)/s .We can regard the function Ψ L,s as a distribution for the following reason: Let λ 1 (L) denote the spacing of L. Then, Ψ L,s restricted to [0, λ 1 (L)] is a probability density sinceλ1(L) 0 Ψ L,s (z)dz = 1 s λ1(L) 0 x∈L ρ s (x -z) = 1 s x∈L λ1(L) 0 ρ s (x -z)dz = 1 s ∞ -∞ ρ s (z)dz = 1 .Lemma B.7 (Mill's inequality [77, Proposition 2.1.2]). Let z ∼ N (0, 1). Then for all t > 0, we haveP(|z| ≥ t) = 2 π ∞ t e -x 2 /2 dx ≤ 1 t • 2 π e -t 2 /2 .Lemma B.8 (Periodic Gaussian density bound [71, Claim I.6] ). For any s > 0 and any z ∈ [0, 1) the periodic Gaussian density Ψ Z,s : [0, 1) → R ≥0 satisfies|Ψ Z,s (z) -1| ≤ 2(1 + 1/(πs))e -πs 2 .Proof. By the Poisson summation formula (Lemma 2.1),Ψ Z,s (z) = 1 s x∈Z ρ s (x -z) = y∈Z e -2πizy • ρ 1/s (y) = 1 + y∈Z\{0} e -2πizy • ρ 1/s (y) .Since |e ia | ≤ 1 for any a ∈ R, we have|Ψ Z,s (z) -1| ≤ y∈Z\{0} |e -2πizy | • ρ 1/s (y) ≤ y∈Z\{0} ρ 1/s (y) ≤ 2 e -πs 2 + ∞ 1 e -πs 2 t 2 dt ≤ 2(1 + 1/(πs))e -πs 2 .Lemma B.9 (TV lower bound). There exists a constant C > 0 such that for any γ > 1 and σ > 0,if γσ < C, then TV A σ γ , N (0, 1/(2π)) > 1/2, where A σ γ is the σ-smoothed discrete Gaussian on (1/γ)Z.Proof. For ease of notation, we denoteN (0, 1/(2π)) by Q. Since TV(A σ γ , Q) = sup S∈F |A σ γ (S) - Q(S)|, where F is the Borel σ-algebra on R, it suffices to find a measurable set S ⊂ R such that A σ γ (S) -Q(S) > 1/2. Let C = 1/(12 √ 2 log2) be the constant in the statement of Lemma B.9. Let δ ∈ (0, 1/4) be the smallest number satisfying the condition γσ ≤ δ/(3 log(1/δ)). Such δ > 0 always exists under the given assumptions since δ/ log(1/δ) is increasing in δ and δ = 1/4 satisfies the condition (thanks to our choice of C). We claim that the set S defined below witnesses the TV lower bound.S := z ∈ R | dist(z, L) ≤ σ √ 1 + σ 2 • log(1/δ) , where L = (1/γ √ 1 + σ 2 )Z.We show a lower bound for A σ γ (S) and an upper bound for Q(S). Using the mixture form of the density of A σ γ (Eq.( 4)) and Mill's tail bounds for the univariate Gaussian (Lemma B.7), we have that for each Gaussian component in the mixture A σ γ , at least 1 -δ fraction of its probability mass is contained in S. This is because the component means precisely form the one-dimensional lattice L and S contains all significant neighborhoods of L. Thus, A σ γ (S) ≥ 1 -δ. Now we show an upper bound for Q(S). Recall from Definition B.6 the density of the periodic Gaussian distribution Ψ Z,s . Since S is a periodic set, its mass Q(S) is equal to Ψ Z,s ( S ∩ Z), wheres = γ √ 1 + σ 2 and S = z ∈ R | dist(z, Z) ≤ γσ log(1/δ) . Since s = γ √ 1 + σ 2 > 1, by Lemma B.8 for any z ∈ [0, 1) |Ψ Z,s (z) -1| ≤ 4e -πs 2 < 1/2 .Since γσ ≤ δ/(3 log(1/δ)), it follows thatQ(S) = Ψ Z,s ( S ∩ [0, 1]) ≤ 1 + 4e -πs 2 • 2γσ log(1/δ) < 3γσ log(1/δ) ≤ δ . Therefore, TV(A σ γ , Q) ≥ A σ γ (S) -Q(S) > 1 -2δ > 1/2 .We now establish upper bounds on TV(P u , Q d ) via upper bounds on TV(A σ γ , Q). Lemma B.10 provides a tighter upper bound when min(γ, γσ) = ω( √ log d). In this regime, the sequence (TV(P u , Q d )) d∈N is negligible in d. It is worth noting that Lemma B.10 is not tight since TV(A σ γ , Q) → 0 as σ → ∞, whereas the upper bound only converges to e -πγ 2 .On the other hand, Lemma B.11 provides an upper bound on KL(P u ∥ Q d ) which is useful when σ is large. Note that the KL divergence upper bounds the TV distance through Pinsker's or the Bretagnolle-Huber inequality (see e.g., [14] ). Lemma B.10 (TV upper bound). For any γ > 1 and σ > 0 such that σ ≥ 2/γ, the following holds for the σ-smoothed discrete Gaussian A σ γ and Q = N (0, 1/(2π)).TV(A σ γ , Q) ≲ e -πs 2 ,wheres = γσ/ √ 1 + σ 2 .Proof. By the L 1 -characterization of the TV distance,TV(A σ γ , Q) = 1 2 |A σ γ (x) -Q(x)|dx = 1 2 Q(x)|T σ γ (x) -1|dx ,where the likelihood ratio T σ γ is given by (see Eq.( 5))T σ γ (x) = √ 1 + σ 2 σρ((1/γ)Z) k∈Z ρ σ (x -1 + σ 2 k/γ) = √ 1 + σ 2 σρ((1/γ)Z) k∈Z ρ γσ/ √ 1+σ 2 (γx/ 1 + σ 2 -k) .The likelihood ratio is also a re-scaled version of the periodic Gaussian density sinceEQUATIONPlugging in s = γσ/ √ 1 + σ 2 = γ/ (1/σ 2 ) + 1 to Eq.( 20), we haveT σ γ (x) = γ ρ((1/γ)Z) • Ψ Z,s (γx/ 1 + σ 2 ) .The assumption σ ≥ 2/γ implies that s ≥ 1. Thus, by Lemma B.8EQUATION) Since ρ((1/γ)Z) = ρ γ (Z) = γΨ Z,γ (0) and γ > 1, by Lemma B.8 applied to Ψ Z,γ , ρ((1/γ)Z) γ -1 ≤ 2(1 + 1/(πγ))e -πγ 2 < 3e -πγ 2 < 1/4 .We may thus write ρ((1/γ)Z)/γ = 1 + ε for some ε ∈ R such that |ε| ≤ 3e -πγ 2 < 1/4. Then,γ ρ((1/γ)Z) -1 = 1 1 + ε -1 = ε 1 + ε < (4/3)ε .Applying the above inequalities to Eq.( 21), we have that for any x ∈ R,|T σ γ (x) -1| ≤ γ ρ((1/γ)Z) • 3e -πs 2 + γ ρ((1/γ)Z) -1 < (1 + 3e -πγ 2 ) • 3e -πs 2 + 4e -πγ 2 ≤ 4(e -πs 2 + e -πγ 2) .Since 0 < s < γ, it follows thatTV(A σ γ , Q) ≤ 4(e -πs 2 + e -πγ 2 ) ≤ 8e -πs 2 .Lemma B.11 (KL upper bound). For any γ > 0 and σ > 0, the following holds for the σ-smoothed discrete Gaussian A σ γ and Q = N (0, 1/(2π)).KL(A σ γ ||Q) ≤ log( 1 + σ 2 /σ) ≤ 1 2σ 2 .Expressed in terms of the time with respect to the OU process e -t = 1/ √ 1 + σ 2 , for any t > 0KL(A σ γ ∥ Q) ≤ e -2t 2(1 -e -2t) .Proof. By Jensen's inequality and the fact that for anyx ∈ R, T σ γ (x) ≤ T σ γ (0). KL(A σ γ ||Q) = E x∼A σ γ [log T σ γ (x)] ≤ log E x∼A σ γ T σ γ (x) ≤ log T σ γ (0) = log √ 1 + σ 2 σρ γ (Z) • ρ s (Z) ,where s = γσ/ √ 1 + σ 2 < γ.If 0 ≤ s 1 ≤ s 2 , then ρ s1 (Z) ≤ ρ s2 (Z). Hence, ρ s (Z)/ρ γ (Z) ≤ 1.Using the fact that log(1 + a) ≤ a for any a > -1, we haveKL(A σ γ ∥ Q) ≤ log( 1 + σ 2 /σ) = (1/2) log(1 + 1/σ 2 ) ≤ 1/(2σ 2 ) .The second part of the lemma follows straightforwardly from the relation σ/√ 1 + σ 2 = √ 1 -e -2t. Using the fact that log(1 -a) ≥ -a/(1 -a) for any a < 1, for any t > 0 we haveKL(A σ γ ∥ Q) ≤ log(1/ 1 -e -2t ) = -(1/2) log(1 -e -2t ) ≤ e -2t 2(1 -e -2t) .We show that score estimation reduces to parameter estimation for Gaussian pancakes. Given that the sample complexity of parameter estimation for Gaussian pancakes is polynomial in the relevant problem parameters (Theorem 4.2), our reduction implies that the sample complexity of score estimation is polynomial as well.Lemma C.1 (Lemma 4.1 restated). For any γ > 1, σ > 0, let P u be the (γ, σ)-Gaussian pancakes distribution with secret direction u ∈ S d-1 . Given any η ∈ (0, 1) and û ∈ S d-1 such that 1 -⟨ û, u⟩ 2 ≤ η 2 , the score estimate ŝ(x) = -2πx + ∇ log T σ γ (⟨x, û⟩) satisfiesE x∼Pu ∥ŝ(x) -s(x)∥ 2 ≲ max(1, 1/σ 8 ) • η 2 d , where s(x) = -2πx + ∇ log T σ γ (⟨x, u⟩) is the score function of P u .Proof. For simplicity, we omit super and subscripts of the likelihood ratio T σ γ and simply denote it by T . Let û be an estimate satisfying 1 -⟨ û, u⟩ 2 ≤ η 2 and denote û = ⟨ û, u⟩u + w. Note that w ∈ R d is orthogonal to u and ∥w∥ 2 = 1 -⟨ û, u⟩ 2 ≤ η 2 . Then, we haves(x) -ŝ(x) = T ′ (⟨x, u⟩) T (⟨x, u⟩) u - T ′ (⟨x, û⟩) T (⟨x, û)⟩ û = T ′ (⟨x, u⟩) T (⟨x, u⟩) - T ′ (⟨x, û⟩) T (⟨x, û)⟩ ⟨u, û⟩ u - T ′ (⟨x, û⟩) T (⟨x, û)⟩ wBy the triangle inequality and the fact that (a + b) 2 ≤ 2a 2 + 2b 2 for any a, b ∈ R, we haveEQUATIONBy Lemma B.5 and the fact that (1 + σ 2 )/σ 2 ≤ 2 max(1, 1/σ 2 ), we know that the Lipschitz constant L of T ′ /T satisfies L ≲ max(1, 1/σ 4 ). Furthermore, by Eq. ( 13) in Lemma B.5, we have∥T ′ /T ∥ ∞ ≲ max(1, 1/σ 2 ). Applying these upper bounds to Eq.( 22), ∥s(x) -ŝ(x)∥ 2 ≲ T ′ (⟨x, u⟩) T (⟨x, u⟩) - T ′ (⟨x, û⟩) T (⟨x, û)⟩ 2 + T ′ (⟨x, û⟩) T (⟨x, û)⟩ 2 η 2 ≲ max(1, 1/σ 8 )(⟨x, u -û⟩ 2 + η 2 ) ≤ max(For parameter estimation, we design a contrast function g : R → R such that the (population) functionals G and E, defined below, are monotonic. For any γ > 0, u ∈ S d-1 , and (γ, 0)-Gaussian pancakes P u , we defineEQUATIONEQUATIONNote that E(v) = G(σ), where σ 2 = (1 -⟨u, v⟩ 2 )/⟨u, v⟩ 2 . We choose g so that G(σ) is decreasing in σ and E(v) is increasing in ⟨u, v⟩ 2 . We use g = T β γ for some appropriately chosen β > 0. The monotonicity property ofT β γ is shown in Lemma C.3. Thus, given two candidate directions v 1 , v 2 , if E(v 1 ) ≥ E(v 2 ), then ⟨u, v 1 ⟩ 2 ≥ ⟨u, v 2 ⟩ 2 .This suggests the projection pursuitbased estimator û = arg max v∈C Ê(v), where C is an η-net of the parameter space S d-1 andÊ(v) = (1/n) n i=1 T β γ (⟨x i , v⟩)is the empirical version of E. The main theorem of this section (Theorem 4.2) shows that n = poly(d, γ, 1/η) samples is sufficient for achieving L 2 -error η using the estimator û. We start with a useful fact about σ-smoothed likelihood ratios T σ γ . Claim C.2. For any β > 0, σ ≥ 0, and x ∈ R,E z∼Q T β γ 1 √ 1 + σ 2 x + σ √ 1 + σ 2 z = T s γ (x) ,where s = (1 + β 2 )(1 + σ 2 ) -1 and T σ γ denotes the likelihood ratio of the σ-smoothed discrete Gaussian A σ γ on (1/γ)Z with respect to Q = N (0, 1/(2π)) (see Eq. ( 5)).Proof. Let x = x/ √ 1 + σ 2 , σ = σ/ √ 1 + σ 2 , and c k (x) = x -1 + β 2 k/γ. Then, E Q T β γ x + σz = 1 + β 2 βρ((1/γ)Z) ρ(z) k∈Z ρ β x + σz -1 + β 2 k/γ dz = 1 + β 2 βρ((1/γ)Z) k∈Z ρ β/ √ β 2 +σ 2 (z -c k (x))dz • ρ √ β 2 +σ 2 (c k (x)) = 1 + β 2 β 2 + σ2 • ρ((1/γ)Z) k∈Z ρ √ β 2 +σ 2 (x -1 + β 2 k/γ) .Plugging in x = x/ √ 1 + σ 2 and σ = σ/ √ 1 + σ 2 gives usE Q T β γ 1 √ 1 + σ 2 x + σ √ 1 + σ 2 z = √ 1 + s 2 sρ((1/γ)Z) k∈Z ρ s (x -1 + s 2 k/γ) = T s γ (x),where s = (1 + β 2 )(1 + σ 2 ) -1.Lemma C.3 (Monotonicity). Given any γ > 0 and β > 0, define G(σ):= E x∼A σ γ [T β γ (x)], where T σ γ denotes the likelihood ratio of the σ-smoothed discrete Gaussian A σ γ on (1/γ)Z with respect to N (0, 1/(2π)). Then, for any σ > 0, we have G ′ (σ) < 0.Proof. Let T 0 γ (x) = ∞ k=0 α 2k h 2k (x)be the (formal) Hermite expansion of T 0 γ (x), where (h k ) k∈N form an orthonormal sequence with respect to ⟨•, •⟩ Q . By Claim C.2, for any σ ≥ 0EQUATION)Using the orthonormality of (h k ), for any σ > 0G(σ) = E x∼A σ γ [T β γ (x)] = ⟨T β γ , T σ γ ⟩ Q = ∞ k=0 α 2 2k • 1 (1 + β 2 ) k (1 + σ 2 ) k G ′ (σ) = - ∞ k≥1 α 2 2k • 1 (1 + β 2 ) k • 2kσ (1 + σ 2 ) k+1 < 0 .Lemma C.4 (Non-trivial Hermite coefficient). Let (h k ) be the normalized Hermite polynomials with respect to ⟨•, •⟩ Q . For any γ > 1 such that πγ 2 ∈ N and ℓ ∈ N, it holds thatE x∼Aγ h 2πℓ 2 γ 2 (x) ≥ 1 √ 2πℓγ ,where A γ is the discrete Gaussian on (1/γ)Z.Proof. Let (H k ) be the unnormalized Hermite polynomials defined byH k (x)ρ(x) = (-1) k d k dx k ρ(x) .Using the relation between the Fourier transform and differentiation, we haveF{H k (x)ρ(x)} = F (-1) k d k dx k ρ(x) = (-2πiy) k ρ(y) .Let h k = c k H k be the normalized Hermite polynomials, where c k = (2π) k k! (see e.g., [64, Chapter 4.2.1] ). By the Poisson summation formula (Lemma 2.1), we haveE x∼Aγ h k (x) = 1 ρ((1/γ)Z) x∈(1/γ)Z c k H k (x)ρ(x) = γc k ρ((1/γ)Z) y∈γZ (-2πiy) k ρ(y) .We now analyze the maximum among the terms inside the sum. Let f (y) = y k ρ(y). Note that f (y) = y k ρ(y) = (2π) k exp(-πy 2 + k log y) .The exponent in the above expression is maximized at 2π(y * ) 2 = k. This maximum is indeed achieved in the sum since we can choose y * = ℓγ, which is permissible given the assumption πγ 2 ∈ N. Hence, the maximum value of f (y) isf (y * ) = exp(-k/2 + (k/2) log(k/2π)) = (k/2eπ) k/2 .Plugging in the value c k = 1/ (2π) k k! and using the Stirling lower bound k! ≥ √ 2πk(k/e) k for all k ∈ N,E x∼Aγ h k (x) ≥ 2γ ρ((1/γ)Z) c k (2π) k (k/2eπ) k/2 = 2γ ρ((1/γ)Z) c k (2πk/e) k/2 = 2γ ρ((1/γ)Z) • (k/e) k/2 √ k! ≥ 2γ ρ((1/γ)Z) • 1 (2πk) 1/4 .In addition, we have that ρ((1/γ)Z) = γρ(γZ) ≤ γρ(Z) ≤ 2γ .Plugging in k = 2πℓ 2 γ 2 , we therefore haveE x∼Aγ h k (x) ≥ 1 √ 2πℓγ .Corollary C.5 (Non-trivial Hermite coefficient, rounded degree). Let (h k ) be the normalized Hermite polynomials with respect to ⟨•, •⟩ Q . For any γ > 1, ℓ ∈ N, and k = 2⌊ℓ 2 πγ 2 ⌋, it holds thatE x∼Aγ h k (x) ≥ 1 e √ 2πℓγ ,where A γ is the discrete Gaussian on (1/γ)Z.Proof. Let ℓ 2 πγ 2 -⌊ℓ 2 πγ 2 ⌋ = α. Then, α ∈ [0, 1) and k = ℓ 2 (2πγ 2 ) -2α. Similar to the proof of Lemma C.4, we apply the Poisson summation formula (Lemma 2.1) as follows.E x∼Aγ h k (x) = 1 ρ((1/γ)Z) x∈(1/γ)Z h k (x)ρ(x) = γ ρ((1/γ)Z) y∈γZ c k (-2πiy) k ρ(y) .As previously shown in Lemma C.4, the function f (y) = y k ρ(y) achieves its maximum at (y * ) 2 = k/2π = ℓ 2 γ 2 -α/π. The issue now is that y * is not necessarily contained in γZ. However, we show that "rounding up" y * to sγ is sufficient to establish a non-trivial lower bound. Taking the ratio of f (y * ) and f (sγ),log f (sγ)/f (y * ) = k log ℓγ y * -π(ℓ 2 γ 2 -(y * ) 2 ) ≥ -α > -1 .Hence, f (sγ) > f (y * )/e. Combining this observation and the proof of Lemma C.4 leads to the conclusion.Theorem C.6 (Theorem 4.2 restated). For any constant C > 0, given γ(d) > 1, σ(d) > 0 such that γσ < C, estimation error parameter η > 0, and δ ∈ (0, 1), there exists a brute-force search estimator û : R d×n → S d-1 that uses n = poly(d, γ, 1/η, 1/δ) samples and achieves ∥ û(x 1 , . . . , x n ) -u∥ 2 ≤ η 2 with probability at least 1 -δ over i.i.d. samples x 1 , . . . , x n ∼ P u , where P u is the (γ, σ)-Gaussian pancakes distribution with secret direction u ∈ S d-1 .Proof. Without loss of generality, we assume η ≤ 1/γ. If the given error parameter η is larger than 1/γ, we set η = 1/γ. Let C be any η-net of S d-1 . Our brute-force search estimator isû = arg max v∈C Ê(v) , where Ê(v) = 1 n n i=1 T β γ (⟨x i , v⟩) .We choose β = 1/ √ πγ as the contrast function parameter for reasons explained later. The population limit of Ê is E (Eq.( 24)), and the monotonicity of E with respect to ⟨u, v⟩ 2 (Lemma C.3) implies that u = arg max S d-1 E(v) in the infinite-sample limit. For x ∼ P u , the distribution of ⟨x, v⟩ is A ξ γ , whereξ 2 = (1 + σ 2 )/⟨u, v⟩ 2 -1. Let v 1 , v 2 ∈ S d-1 be such that ⟨u, v 1 ⟩ 2 -⟨u, v 2 ⟩ 2 = ε 2 . Let ξ 2 1 = (1 + σ 2 )/⟨u, v 1 ⟩ 2 -1 and ξ 2 2 = (1 + σ 2 )/⟨u, v 2 ⟩ 2 -1. Notice that 1 1 + ξ 2 1 - 1 1 + ξ 2 2 = ε 2 1 + σ 2 .For ε-far pairs v 1 , v 2 such that ξ 1 is sufficiently small, we establish a lower bound on E(v 1 ) -E(v 2 ) in terms of ε. This implies that if E(v 1 ) and E(v 2 ) are close, then ⟨u, v 1 ⟩ 2 and ⟨u, v 2 ⟩ 2 are also close.By Claim C.2, for any v ∈ S d-1 , we haveE(v) = ⟨T ξ γ , T β γ ⟩ Q = ∞ k=0 α 2 2k • 1 (1 + β 2 ) k (1 + ξ 2 ) k .Since all the terms in the series are non-negative and monotonically decreasing in ξ, for any k ∈ N and v 1 , v 2 ∈ S d-1 such that ξ 1 ≤ ξ 2 , we haveE(v 1 ) -E(v 2 ) ≥ α 2 2k (1 + β 2 ) k 1 1 + ξ 2 1 k - 1 1 + ξ 2 2 k = α 2 2k (1 + β 2 ) k (1 + ξ 2 1 ) k 1 - 1 + ξ 2 1 1 + ξ 2 2 1 + ξ 2 1 1 + ξ 2 2 k-1 + 1 + ξ 2 1 1 + ξ 2 2 k-2 + • • • + 1 ≥ α 2 2k (1 + β 2 ) k (1 + ξ 2 1 ) k ε 2 (1 + ξ 2 1 ) 1 + σ 2 ≥ α 2 2k (1 + β 2 ) k (1 + ξ 2 1 ) k-1 ε 2 1 + σ 2 We choose k = ⌊πγ 2 ⌋, β 2 = 1/k. If ξ 21 ≤ C ′ /k for some constant C ′ > 0 (this will be justified later), then by Corollary C.5, we have that α 2 2k ≥ 1/(2πe 2 γ). Thus, using the fact that 1 + t ≤ e t for any t ∈ R,EQUATION) Taking the contrapositive, if v 1 , v 2 ∈ S d-1 are such that ξ 1 ≤ ξ 2 , ξ 2 1 ≤ C ′ /k and E(v 1 ) -E(v 2 ) ≤ ε 2 /(2π(1 + C 2 )e C ′ +3 γ), then ⟨u, v 1 ⟩ 2 -⟨u, v 2 ⟩ 2 ≤ ε 2 .Equipped with this result, we revisit our η-net C of S d-1 . Let v * = arg max v∈C E(v) be the population maximizer of E within C. By the monotonicity of E(v) with respect to ⟨u, v⟩ 2 , we have that 1 -⟨u, v * ⟩ 2 ≤ η 2 /2. Moreover, since by assumptionEQUATION)Now consider û = arg max v∈C Ê(v), the maximizer of the empirical objective. By the triangle inequality,EQUATIONWe show that both terms in Eq.( 28) concentrate. Recall that It follows that E(v * ) -E( û) ≲ η 2 /γ with probability 1 -δ over the randomness of û. Since v * satisfies (ξ * ) 2 ≲ 1/γ 2 (see Eq.( 27)) and ξ * ≤ ξ, where we denote ξ 2 = (1 + σ 2 )/⟨u, û⟩ 2 -1, the closeness of E(v * ) and E( û) implies ⟨u, v * ⟩ 2 -⟨u, û⟩ 2 ≤ η 2 due to Eq.( 26). Hence,Ê(v) = (1/n) n i=1 T β γ (⟨v, x i ⟩) and that the function T β γ satisfies (see proof of Lemma B.11) T β γ (z) ≤ T β γ (0) = 1 + β 2 βρ((1/γ)Z) • ρ(( 1 + β 2 /βγ)Z) ≤ 1 + β 2 /β .∥u -û∥ 2 = 2(1 -⟨u, û⟩ 2 ) ≤ 2η 2 + 2(1 -⟨u, v * ⟩ 2 ) ≤ 3η 2 .Answer: [NA] Justification: This is a purely theoretical paper with no experiments. Guidelines:• The answer NA means that paper does not include experiments requiring code. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: This is a purely theoretical paper with no experiments. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our work does not involve any release of data or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use any assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.An animated visualization of Gaussian pancakes can be found in[12].Note, however, that algorithms that run in time T can query the sampling oracle at most T times, so the running time imposes a limit on the number of samples the algorithm can see.The usual choice is √ 2, for which the stationary distribution is N (0, I d ).To be precise, f must satisfy some niceness conditions; this will always hold in our applications. 
 
 Appendix:  


Decision: The paper shows a statistical to computational gap for L2 score estimation under standard cryptographic assumptions. Reviewers agree this is an interesting and valuable contribution to understanding the computational complexity of problems related to diffusion models

Reviews: review: paper_summary: paper_summary: Without knowing data distribution, it is computationally hard to estimate score function from data samples, such as the reverse step of diffusion models. One previous work shows that L^2-accurate score estimation along the forward process can help efficiently sampling from arbitrary data distribution. However, this works shows L^2-accurate score estimation is still computationally hard even with polynomial sample complexity. Finding a gap between statistical perspective and computational perspective leads to a set of hard distributions, which are “Gaussian pancakes” distributions. This works conclude computationally efficient  L^2-accurate score estimation should rely on stronger assumptions.
strength_weakness: strength_weakness: This work is lack of empirical evidences, especially those related to diffusion models.
questions: questions: Can you remove one “between” in Line 32?
limitations: limitations: None limitation has been detected.
paper_summary: paper_summary: This paper shows that $L^2$-accurate score estimation, a crucial primitive in the theory of diffusion models and sampling, is computationally hard in the worst-case. The main theorem is a negative result that provides a statistical-computational gap: if computationally efficient $L^2$-accurate score estimation is possible, then one has a computationally efficient algorithm for solving the *Gaussian pancakes problem*, a hard instance under widely believed hardness assumptions from lattice-based cryptography. This negative result is particularly important in relation to Chen et al. (2023), as they showed that access to an $L^2$-accurate score estimation oracle (with some mild additional assumptions) admits an algorithm for sampling from any arbitrary distribution. The computational hardness of such an oracle suggests future directions for research in making stronger assumptions so such an oracle *is* possible (omitting the worst-case instance of Gaussian pancakes) or weaker criteria for understanding when a sample generated from the DDPM process is "good enough."

The main result, Theorem 3.1, is proven mainly by way of using Theorem 2 of Chen et al. (2023), which states that, for any distribution, the output of the DDPM algorithm provides a certificate for Gaussianity. Importantly, this DDPM algorithm assumes access to an $L^2$-accurate score estimation oracle, so by using this certificate of Gaussianity on the particular choice of the Gaussian pancake distribution, we can distinguish just by using the certificate of Gaussianity as a test statistic. Theorem 4.2 also gives the sample complexity of estimating the Gaussian pancake distribution through a brute force search over the possible hidden directions.
strength_weakness: strength_weakness: The paper was well-written and I could not find any typographical or clarity issues. To the best of my checking, the theorem seemed correct, and its proof outline provided insight into the argument. I am an outsider to the literature, so I would not be confident in critiquing the paper in terms of weaknesses. As far as I can see, it the paper is clear, the theorem is well-motivated, and the argument is correct.

If anything, one might critique that perhaps the work would be more complete with a positive result towards a distribution-specific narrowing of DDPM that avoids the Gaussian pancakes distributions. However, I have no gauge on how hard/standard this might be in the literature, and it seems that $L^2$-accurate score estimation is central enough a primitive in DDPM that this negative result is important in its own right.
questions: questions: I have a couple of main questions, but they may stem from my ignorance of the literature:

1. Because the Gaussian pancakes class is hard, I assume that there have been positive results in the light of this computationally hard instance in other problems that exclude this class. What are examples of such distribution-specific guarantees?
2. How does the "weaker criteria for evaluating sample quality" in Section 1.3 relate to the Theorem 4.2? Is there still a statistical-computational gap if we allowed "distinguish" to be a looser requirement?
limitations: limitations: The authors have addressed the limitations of the work in the NeurIPS paper checklist. Because this is mainly a theory paper, I do not see it as having other ethical conflicts.
paper_summary: paper_summary: This paper investigates the difficulty of distinguishing a Gaussian pancake distribution from a Gaussian distribution from the perspective of score estimation. The authors show that, by assuming the $L^2$-error of the score estimation is of the order $\log(d)$, there is a polynomial-time algorithm that solves the Gaussian pancake problem. Moreover, they show that for the cryptographically hard regime, there is a polynomial sample complexity $O(d)$ that ensures a small score estimation error for Gaussian pancake problems.
strength_weakness: strength_weakness: One main selling point, which has been emphasized repeatedly in the paper and is also the title of this paper, is that the score estimation is cryptographically hard. This is confusing to me. In fact, as I understand it, the main theorem states that the Gaussian pancake problem can be solved under certain assumptions, while the hardness seems to state that the score estimation is hard.

If I understand correctly, the hardness arises from the assumption that $\gamma\sigma = O(1)$ in Theorem 4.2, which is known to be hard in existing literature, while the score estimation has a polynomial upper bound. However, I cannot see the hardness from Theorem 4.2. Even though the Gaussian pancake problem is hard, the score estimation is accurate. If we further combine Theorem 4.2 with Theorem 3.1, I guess the authors want to argue that if the score estimation is easy, then the Gaussian pancake problem can be solved. However, as it is already known that the Gaussian pancake problem is hard, the score estimation cannot be easy. But the score estimation error assumption in Theorem 3.1 does not match Theorem 4.2's conclusion. In fact, the $O(\log d)$ assumptions of Theorem 3.1 on the estimation error are smaller than the polynomial $O(d)$ upper bound in Theorem 4.2, which may make the story incomplete.

Please correct me if my understanding is incorrect.
questions: questions: please solve my concern in the weaknesses part
limitations: limitations: Yes

Comments: comment: Thank you to the authors for providing such a comprehensive response to my questions! This was an interesting foray into literature that I was not previously exposed to, and I appreciate the authors for engaging. I remain positive in my evaluation of the work, and best of luck to the authors. Thank you for providing an interesting read.