The discrete Gaussian @math is the distribution that assigns to each vector @math in a shifted lattice @math probability proportional to @math . It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomial-time algorithms for DGS with very high parameters @math have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed @math -time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. There is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when @math ) to SVP. In the other direction, there is a simple reduction from @math -approximate SVP for any @math , and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor. We also show that our CVP result extends to a much wider class of distributions and even to other norms.
The samplers in this work approach discrete Gaussian sampling in a completely different way. (Indeed, the author repeatedly tried and failed to modify the above techniques to work in our context.) Instead, as we described above, we use a new method of sampling based on lattice sparsification. This tool was originally introduced by Khot for the purposes of proving the hardness of approximating SVP @cite_8 . Khot analyzed the behavior of sparsification only on the specific lattices that arose in his reduction, which were cleverly designed to behave nicely when sparsified. Later, Dadush and Kun analyzed the behavior of sparsification over general lattices @cite_32 and introduced the idea of adding a random shift to the target in order to obtain deterministic approximation algorithms for CVP in any norm. Dadush, Regev, and Stephens-Davidowitz used a similar algorithm to obtain a reduction from approximate CVP to the same problem with an upper bound on the distance to the lattice (and a slightly smaller approximation factor) @cite_49 . Our sparsification analysis in the CVP case is most similar to that of @cite_49 , though our reduction requires tighter analysis.
@cite_32 @cite_49 @cite_8
2069278600 1624710162 2146007300 2762725970
We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n sqrt log n ), improving on the previous best of O(n^ 1.5 ) due to Lag arias, Lenstra, and Schnorr hkzbabai . We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(sqrt n log n ) due to Aharonov and Regev AharonovR04 . To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio LiuLM06 gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+eps)gamma approximate CVP to gamma approximate CVP where the target is at distance at most 1+1 eps times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun DadushK13 . As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice MR04 . We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide tilde Omega (sqrt n ) factor larger. We give a 2 n+o(n) -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic a#x007E; O (4n)-time and a#x007E; O (2n)-space algorithm of Micciancio and Voulgaris. We achieve our main result in three steps. First, we show how to modify the sampling algorithm due to Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) to solve the problem of discrete Gaussian sampling over lattice shifts, L-t, with very low parameters. While the actual algorithm is a natural generalization of ADRS, the analysis uses substantial new ideas. This yields a 2n+o(n)-time algorithm for approximate CVP with the very good approximation factor a#x03B3; = 1+2-o(n log n). Second, we show that the approximate closest vectors to a target vector can be grouped into "lower-dimensional clusters," and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that "behaves well with these clusters." Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest. We give a deterministic algorithm for solving the (1 + e) approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2O(n) (1 + 1 e)n time and 2n poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the "AKS Sieve" based algorithms for (1 + e)-CVP (Ajtai, Kumar, and Sivakumar; STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2O(n) time algorithm for exact CVP in the l2 norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for "spar-sifying" any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003) for the purpose of proving hardness for Shortest Vector Problem (SVP) under lp norms. In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the Wasserstein-2 distance. Our guarantees improve or extend the state-of-the-art results in three directions. First, we provide an upper bound on the error of the first-order Langevin Monte Carlo (LMC) algorithm with optimized varying step-size. This result has the advantage of being horizon free (we do not need to know in advance the target precision) and to improve by a logarithmic factor the corresponding result for the constant step-size. Second, we study the case where accurate evaluations of the gradient of the log-density are unavailable, but one can have access to approximations of the aforementioned gradient. In such a situation, we consider both deterministic and stochastic approximations of the gradient and provide an upper bound on the sampling error of the first-order LMC that quantifies the impact of the gradient evaluation inaccuracies. Third, we establish upper bounds for two versions of the second-order LMC, which leverage the Hessian of the log-density. We nonasymptotic guarantees on the sampling error of these second-order LMCs. These guarantees reveal that the second-order LMC algorithms improve on the first-order LMC in ill-conditioned settings.