One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time

Jiseung Kim

REVIEW 2 major objections 2 minor 17 references

One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time

T0 review · 2 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that one sample from any discrete Gaussian can be drawn in $2^{n/2+o(n)}$ time and space, resolving the ADRS open question and yielding faster exact SVP and close-target CVP.

desk verdict The random-superlattice idea is genuinely good and the main theorem may well be right, but the paper leans on an ADRS running-time import I cannot square with the authors' own abstract, and the application constants have a real numerical inconsistency. read the letter →

arxiv 2608.03220 v1 pith:ZCWOIHFJ submitted 2026-08-04 cs.DS

Jiseung Kim This is my paper · ORCID

classification cs.DS MSC 11H0668Q1768W20

keywords discreteGaussiansamplingsmoothingparametersuperlatticesparsificationexactshortestvectorproblemclosestrejectionPoissonsummationlatticealgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper answers an open question left by the ADRS discrete-Gaussian sampler: one sample from $D_{L,s}$ can be drawn at an arbitrary parameter $s$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space, matching a bound that was previously known only above the smoothing threshold. The algorithm does not sample from $L$ directly; it builds a random superlattice that is smooth at a smaller scale, draws the $2^{n/2}$ vectors returned by one ADRS call, and returns the first vector that lies back in $L$. A Gaussian-mass comparison, tight in its $2^{n/2}$ factor, shows the list contains a point of $L$ with inverse-polynomial probability, so the list size exactly cancels the rejection loss. The same comparison yields exact CVP in sub-$2^n$ time for close targets and exact SVP in $2^{0.7315n+o(n)}$ time.

What carries the argument

The load-bearing object is a random superlattice obtained by dual sparsification: choose a uniformly random primitive vector $z\in(\mathbb{Z}/2^m\mathbb{Z})^n$, let $M_z$ be the kernel of $a\mapsto\langle z,a\rangle\bmod 2^m$ on $L^*$, and set $L_z=M_z^*\supseteq L$, a superlattice of index $2^m$. This sparsifies the dual lattice, making $L_z$ smooth at $t=s/\sqrt{2}$ with probability at least $3/4$. The Gaussian-mass estimate $\rho_{\sqrt{2}t}(L_z)\le 40(2m^*-1)2^{n/2}\rho_t(L)$ then converts smoothness into a rejection bound: a sample from $D_{L_z,\sqrt{2}t}$ lands in $L$ with inverse-polynomial probability, so the $N=2^{n/2}$ samples from one ADRS call contain a point of $L$ often enough.

What would settle it

On a small lattice (say rank 2 or 3) with a rational basis, run an exact implementation of the ADRS sampler at a parameter $s$ below $\sqrt{2}\,\eta_{1/2}(L)$, record the list length $M$ and the first returned vector in $L$, and test the joint law against the product of the marginals; any detectable dependence of the first $L$-point on $M$ refutes the independence premise behind Lemma 4.1 and would make Algorithm 2's output deviate from $D_{L,s}$.

Watch

Extended reading notes

Core claim

Theorem 4.3 is the central claim: given a rational basis of a rank-$n$ lattice $L$ and any rational $s^2>0$, Algorithm 2 outputs a vector $\exp(-\Omega(n^3))$-close to $D_{L,s}$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space. The construction samples a random superlattice $L_z$ that is smooth at $t=s/\sqrt{2}$ with constant probability, runs the ADRS sampler on $L_z$ at $\sqrt{2}t$, and returns the first returned vector that lies in $L$. The sampler's list length is independent of the sample values, so conditioning gives exactly $D_{L,s}$. A Gaussian-mass comparison, tight in its $2^{n/2}$ factor, shows the list catches $L$ with inverse-polynomial probability; the same comparison,

Load-bearing premise

The construction rests on the imported guarantee that the ADRS sampler's list length $M$ is chosen independently of the sampled vectors even below the smoothing threshold; if $M$ and the sample values were correlated, the first vector in $L$ would not be distributed as $D_{L,s}$.

Editorial extensions

If this is right

One sample from $D_{L,s}$ can be drawn at every rational scale in time $2^{n/2+o(n)}$ with error $\exp(-\Omega(n^3))$, resolving the ADRS open question.
The factor $2^{n/2}$ in the mass comparison is tight, so the running-time improvement is not an artifact of a loose comparison.
Exact CVP on targets within $\alpha\lambda_1(L)$ for any fixed rational $\alpha<1.4697$ is sub-$2^n$ without a uniqueness assumption; at $\alpha=1$ the exponent is about $0.7315$.
Exact SVP runs in time $2^{0.7315n+o(n)}$ and space $2^{n/2+o(n)}$.
Any sampler meeting the ADRS guarantee with $N=2^{\xi n}$ outputs at cost $2^{\omega n}$ per call and $2^{\zeta n}$ space gives exact SVP in time $2^{(\omega+\max\{0,1/2+\delta-\xi\})n}$, where $\delta\approx0.2315$, isolating sampling cost from repetition count.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The superlattice-rejection pattern may transfer to other distributions whose envelope can be smoothed at a slightly smaller scale, provided the sampler's list length stays independent of the values.
Because the exact-SVP exponent depends on the spherical-code constant through $\delta$, any future improvement to that constant would automatically lower $2^{0.7315n+o(n)}$ within the same framework.
The paper itself notes two boundaries: it stores one ADRS output list of size $2^{n/2+o(n)}$, and the construction is centered—arbitrary-parameter shifted DGS is not reached because $\rho_s(L-y)/\rho_s(L)$ can be arbitrarily small.
Tightness of the $2^{n/2}$ comparison suggests this rejection route cannot be pushed below $2^{n/2}$ for one sample; a different mechanism would be needed for a faster one-sample DGS.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

If the imported ADRS guarantee is correct, this paper answers the open question cleanly: the random-superlattice construction, the Gaussian-mass comparison, and the "first point in L" extraction are new, and the proof around them is careful. The tightness observation (Theorem 3.8) is a nice addition, and the Turing-machine implementation section is more thorough than most papers in this area. I would want this in front of a referee even if I have doubts.

The doubts are real, though. The load-bearing import is Theorem 2.6, which says ADRS gives 2^{n/2+o(n)} time for every input, with only the list length M changing below threshold. But the paper's own introduction says ADRS at arbitrary parameter costs 2^{n+o(n)}, and only above smoothing costs 2^{n/2+o(n)}. Algorithm 2 loops over J moduli and makes T repetitions at each, and the proof of Theorem 4.3 says every call costs 2^{n/2+o(n)} by Theorem 2.6. If below-smoothing ADRS really costs 2^{n+o(n)}, then the calls at m < m* alone kill the claimed bound. The paper does not re-prove Theorem 2.6 or quote a matching statement from ADRS. This is not a trivial citation issue; it is the difference between resolving the question and not. The authors need to pin down exactly what ADRS Theorem 5.11 says, including whether the independence of M in Definition 2.5 holds. Without that independence, Lemma 4.1 and the entire distributional argument fail.

There is also a smaller, obvious fix needed in Section 6. The paper defines μ = β_Lev^2/(2 e ln 2), but the stated approximation 0.4629 matches β_Lev^2/(2 ln 2). The values of c0 and 1/sqrt(μ) are off accordingly. The main theorem does not depend on those constants, but the CVP/SVP claims do, and the exponents advertised in the abstract need rechecking.

Who is this for? Lattice algorithms people, especially anyone working on DGS and exact SVP/CVP. If the ADRS import is repaired, this is a significant result. As written, the main theorem is conditional on a theorem statement that looks wrong from the paper's own framing.

My recommendation: send it to peer review. A referee should force the authors to state exactly what ADRS proves and to fix the constants. If Theorem 2.6 cannot be supported, the central claim collapses; if it can, this is a strong paper.

Referee Report

2 major / 2 minor

Summary. The paper gives an algorithm that, given a rational basis of a full-rank lattice L and a rational squared parameter s^2>0, outputs one vector within statistical distance exp(-Ω(n^3)) of the discrete Gaussian D_{L,s}, in expected 2^{n/2+o(n)} time and 2^{n/2+o(n)} space on every execution. The method embeds L in a random superlattice L_z chosen by dual sparsification, argues that L_z is smooth at t=s/√2 with constant probability, calls the ADRS sampler on L_z at parameter √2t, and returns the first sampled vector that lies in L. A Gaussian-mass comparison gives inverse-polynomial success probability per call. The paper also derives applications to exact CVP for close targets and to exact SVP, claiming sub-2^n CVP for α<1.4697 and SVP in 2^{0.7315n+o(n)} time.

Significance. If correct, Theorem 4.3 resolves the ADRS open question affirmatively: one discrete Gaussian sample at an arbitrary parameter is obtainable at the above-smoothing cost. The core construction is elegant, and the paper is unusually careful about randomized Turing-machine implementation, certified arithmetic, and space bounds on every execution. The tightness statement in Theorem 3.8 is a valuable addition. However, the main time bound relies on an imported ADRS theorem whose statement appears in tension with the paper's own abstract, and Section 6 contains an internal numerical inconsistency in the constants that propagates to the advertised application exponents. These points need to be resolved before the claims can be accepted.

major comments (2)

[Section 2 (Theorem 2.6) and Section 4 (Algorithm 2, Theorem 4.3)] The running-time assertion of Theorem 2.6, 'running time and space are 2^{n/2+polylog(κ)+o(n)}', is stated without the threshold condition, although Definition 2.5 only forces M=N when s>φ(L). The paper's own abstract says ADRS's arbitrary-parameter sampler costs 2^{n+o(n)} and only the above-smoothing sampler costs 2^{n/2+o(n)}. This distinction is load-bearing: Algorithm 2 loops over all m=1..J (line 6), and for m<m* the superlattice L_z is not guaranteed to be smooth at t, so the calls at s=√2t are below φ(L_z). Under the actual ADRS guarantee those calls would cost 2^{n+o(n)} each, and there are J·T=O(J^2κ0) such calls per iteration, giving 2^{n+o(n)}poly(n,β_s) rather than 2^{n/2+o(n)}. The proof of Theorem 4.3 says 'Each call costs 2^{n/2+o(n)} ... by Theorem 2.6' but does not address the modulus range; Section 5.3 only sums costs per call and absorbs J as a polynomial factor. Plea
[Section 6, constants before Lemma 6.1] With cLev≈0.4014 and βLev=2cLev≈0.8028, the displayed value μ=βLev^2/(2e ln2) evaluates to ≈0.171, not ≈0.4629. Consequently δ=μ/2 and c0=1/2+δ are ≈0.0855 and ≈0.5855, not 0.2315 and 0.7315. These constants are used in Theorem 6.4 (1/√μ≈1.4697), Theorem 6.6 (c0), Theorem 6.7, and the abstract. The stated exponents and thresholds are therefore internally inconsistent with the definitions. Please correct the constants and re-derive the affected statements.

minor comments (2)

[Section 5.1, Lemma 5.3] In the statement of Lemma 5.3, H is defined as ⌈2KT(x)⌉, but the proof's Markov step claims an exceedance probability of 2^{-K}. With the written definition, Markov's inequality gives at most 1/(2K). If the intended definition is H=⌈2^K T(x)⌉, please fix the notation; otherwise the cutoff error is only inverse-polynomial, not exp(-Ω(K)).
[Section 1 and Section 2] The description of the ADRS result in the introduction ('arbitrary parameter in 2^{n+o(n)}; above smoothing in 2^{n/2+o(n)}') should be stated in the same terms as Theorem 2.6, since the current discrepancy is the source of the main technical concern above.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained given the external ADRS sampler and standard Poisson/Gaussian-mass facts.

full rationale

The paper's central algorithm samples from a randomly sparsified superlattice L_z that is smooth at t=s/√2, invokes the ADRS sampler at √2t (above L_z's smoothing threshold), and filters out points not in L. The acceptance probability is bounded by Theorem 3.4 via Poisson summation and dual-mass estimates; no parameter is fitted to the target D_{L,s} distribution. The modulus m* and repetition counts J,T are explicit functions of the input and of rational upper bounds on Θ_t, derived rather than calibrated. Theorem 2.6 is imported from ADRS15 as an external published sampler guarantee, not a self-citation, and the paper does not redefine or rename it; if that guarantee is misstated, the honest criticism is a correctness/soundness one, not constructional circularity. Theorems 3.7–3.8 give a genuine unconditional lower bound on the mass comparison, not a circular use of the upper bound. Section 7's stated limitations (storing one 2^{n/2}-size list; centered, non-shifted DGS) are acknowledged constraints, not hidden circular inputs. Under the review rules, none of the derivation steps reduces to its own inputs, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard Poisson summation, the imported ADRS sampler guarantee, and the DK16 sparsification method, plus the KL/PS09 mass bound for the applications. No numerical parameters are fitted to data; all constants are hardwired from the analysis. The main gap is the numerical inconsistency in Section 6, not free parameters or invented entities.

assumptions (4)

domain assumption ADRS sampler guarantee (Definition 2.5 and Theorem 2.6): a 2^(n/2+o(n))-time sampler that outputs N samples above the threshold sqrt(2)*eta_{1/2}(L), and a random number M of samples below it, with M independent of the sample values.
The whole algorithm builds on this cited theorem. The independence of M is load-bearing for the 'first point in L' distribution argument in Lemmas 4.1 and 4.2. The paper does not re-prove ADRS Theorem 5.11.
standard math Poisson summation identity rho_s(L) = s^n/det(L) * rho_{1/s}(L^*)
Used throughout, explicitly in Equation (2), and in Theorems 3.4, 3.7, 3.8 and the shifted-target analysis.
domain assumption Kabatiansky-Levenshtein spherical-code bound and the effective Gaussian mass bound in Lemma 6.1
The CVP and SVP applications rely on Lemma 6.1, which is proved in Appendix A using KL and PS09. The internal numeric inconsistency in Section 6 concerns quantities derived from this bound.
domain assumption Lattice sparsification by a random kernel from Danush-Kun (DK16), summarized in Lemma 3.1 and 3.2
The paper adapts the DK16 sparsification technique. The existence of the superlattice basis and the inclusion-probability bound for dual vectors are proved in Lemmas 3.1 and 3.2, but the underlying technique is imported.

how reviews work

0 comments

Cite this review

Pith. "Pith review of One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time." pith.science (2026). https://pith.science/paper/ZCWOIHFJ

@misc{pith2026260803220,
  author       = {Pith},
  title        = {Pith review of: One Discrete Gaussian Sample in $2^n/2+o(n)$ Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZCWOIHFJ}},
  note         = {Machine review of arXiv:2608.03220}
}

abstract

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-\Omega(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $\alpha<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\le\alpha\lambda_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 14 canonical work pages

[1]

Fine- grained hardness of CVP(P) – everything that we can prove (and nothing else)

[ABGS21] Divesh Aggarwal, Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. Fine- grained hardness of CVP(P) – everything that we can prove (and nothing else). InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 1816–1835,

work page 2021
[4]

doi:10.1109/FOCS.2015

work page doi:10.1109/focs.2015 2015
[5]

doi:10.1137/1.9781611978315

work page doi:10.1137/1.9781611978315
[10]

[DRS14] Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz

doi: 10.4086/toc.2016.v012a002. [DRS14] Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. InProceedings of the 29th Annual IEEE Conference on Computational Complexity, pages 98–109, 2014.doi:10.1109/CCC.2014.18. [EWY23] Thomas Espitau, Alexandre Wallet, and Yang Yu. On gaussian sampling, smoo...

work page doi:10.4086/toc.2016.v012a002 2016
[12]

26 [GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan

URL:https://eprint.iacr.org/2026/1587. 26 [GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. InProceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 197–206, 2008.doi:10.1145/1374376.1374407. [Hha26] Minki Hhan. Solving the shortest vector problem in 2 0.6039...

arXiv 2026
[13]

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian

URL:https://arxiv.org/abs/2608.02478,arXiv:2608.02478. [Kar16] Charles F. F. Karney. Sampling exactly from the normal distribution.ACM Transactions on Mathematical Software, 42(1):3:1–3:14, 2016.doi:10.1145/2710016. [KL78] G. A. Kabatiansky and V. I. Levenshtein. Bounds for packings on a sphere and in space. Problemy Peredachi Informatsii, 14(1):3–25,

work page Pith review arXiv 2016
[39]

Just take the average! an embarrassingly simple 2 n-time algorithm for SVP (and CVP)

[AS18] Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! an embarrassingly simple 2 n-time algorithm for SVP (and CVP). In1st Symposium on Simplicity in Algorithms (SOSA 2018), volume 61 ofOpen Access Series in Informatics, pages 12:1–12:19. Schloss Dagstuhl– Leibniz-Zentrum f¨ ur Informatik, 2018.doi:10.4230/OASIcs.SOSA.2018.12. [BLP+1...

work page doi:10.4230/oasics.sosa.2018.12 2018
[2007]

[MV13] Daniele Micciancio and Panagiotis Voulgaris

doi:10.1137/S0097539705447360. [MV13] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations.SIAM Journal on Computing, 42(3):1364–1391, 2013.doi:10.1137/100811970. [Nik20] Geno Nikolov. On the extreme zeros of Jacobi polynomials,

doi:10.1137/s0097539705447360 2013

Show all 17 references

[2009]

[PS26] Amaury Pouly and Yixin Shen

URL: https://eprint.iacr.org/2009/605. [PS26] Amaury Pouly and Yixin Shen. Solving the shortest vector problem in 2 0.63269n+o(n) time on random lattices. InAdvances in Cryptology – EUROCRYPT 2026, Part IV, pages 92–123. Springer, 2026.doi:10.1007/978-3-032-25327-9_4. [Ste16] ...

2009 doi
[2013]

[CCL18] Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai

Statement numbers cited in the text follow the full version, arXiv:1306.0281.doi:10.1145/2488608.2488680. [CCL18] Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai. Space-efficient classical and quantum algorithms for the shortest vector problem.Quantum Information and Computation,...

arXiv
[2015]

[ADS15] Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz

Statement numbers cited in the text follow the full version, arXiv:1412.7994.doi:10.1145/2746539.2746606. [ADS15] Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz. Solving the closest vector problem in 2 n time – the discrete Gaussian strikes again! InProceedings o...

arXiv
[2016]

[SZ24] Naser Talebizadeh Sardari and Masoud Zargar

doi:10.1137/1.9781611974331.ch121. [SZ24] Naser Talebizadeh Sardari and Masoud Zargar. New upper bounds for spherical codes and packings.Mathematische Annalen, 389:3653–3703, 2024.doi:10.1007/s00208-023-02738-z. A An effective Gaussian-mass bound This appendix makes the o(n) t...

2024 doi
[2018]

[CDLP13] Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, and Chris Peikert

doi:10.26421/QIC18.3-4-7. [CDLP13] Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, and Chris Peikert. On the lattice smoothing parameter problem. InProceedings of the 28th IEEE Conference on Computational Complexity, pages 230–241, 2013.doi:10.1109/CCC.2013.31. [CSS26] Cl´ emence ...

2013 doi
[2020]

[PS09] Xavier Pujol and Damien Stehl´ e

URL: https://arxiv.org/ abs/2002.02633,arXiv:2002.02633. [PS09] Xavier Pujol and Damien Stehl´ e. Solving the shortest lattice vector problem in time 2 2.465n. Cryptology ePrint Archive, Report 2009/605,

2002 arXiv
[2023]

[GFH26] Yiming Gao, Yansong Feng, and Honggang Hu

doi:10.1007/978-981-99-8739-9_3 . [GFH26] Yiming Gao, Yansong Feng, and Honggang Hu. Solving the shortest vector problem in 20.7314n+o(n) time via discrete Gaussian sampling on superlattices. Cryptology ePrint Archive, Report 2026/1587,

2026 doi
[2025]

[ADRS15] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz

Statement numbers cited in the text follow the full version, arXiv:2002.07955.doi:10.1137/22M1486959. [ADRS15] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2 n time using discrete Gaussian sampling. InProceedi...

2002 arXiv
[2026]

[DK16] Daniel Dadush and G´ abor Kun

URL:https://arxiv.org/abs/2605.20133,arXiv:2605.20133. [DK16] Daniel Dadush and G´ abor Kun. Lattice sparsification and the approximate closest vector problem.Theory of Computing, 12(2):1–34,

arXiv

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

Fine- grained hardness of CVP(P) – everything that we can prove (and nothing else)

[ABGS21] Divesh Aggarwal, Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. Fine- grained hardness of CVP(P) – everything that we can prove (and nothing else). InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 1816–1835,

work page 2021

[2] [4]

doi:10.1109/FOCS.2015

work page doi:10.1109/focs.2015 2015

[3] [5]

doi:10.1137/1.9781611978315

work page doi:10.1137/1.9781611978315

[4] [10]

[DRS14] Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz

doi: 10.4086/toc.2016.v012a002. [DRS14] Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. InProceedings of the 29th Annual IEEE Conference on Computational Complexity, pages 98–109, 2014.doi:10.1109/CCC.2014.18. [EWY23] Thomas Espitau, Alexandre Wallet, and Yang Yu. On gaussian sampling, smoo...

work page doi:10.4086/toc.2016.v012a002 2016

[5] [12]

26 [GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan

URL:https://eprint.iacr.org/2026/1587. 26 [GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. InProceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 197–206, 2008.doi:10.1145/1374376.1374407. [Hha26] Minki Hhan. Solving the shortest vector problem in 2 0.6039...

arXiv 2026

[6] [13]

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian

URL:https://arxiv.org/abs/2608.02478,arXiv:2608.02478. [Kar16] Charles F. F. Karney. Sampling exactly from the normal distribution.ACM Transactions on Mathematical Software, 42(1):3:1–3:14, 2016.doi:10.1145/2710016. [KL78] G. A. Kabatiansky and V. I. Levenshtein. Bounds for packings on a sphere and in space. Problemy Peredachi Informatsii, 14(1):3–25,

work page Pith review arXiv 2016

[7] [39]

Just take the average! an embarrassingly simple 2 n-time algorithm for SVP (and CVP)

[AS18] Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! an embarrassingly simple 2 n-time algorithm for SVP (and CVP). In1st Symposium on Simplicity in Algorithms (SOSA 2018), volume 61 ofOpen Access Series in Informatics, pages 12:1–12:19. Schloss Dagstuhl– Leibniz-Zentrum f¨ ur Informatik, 2018.doi:10.4230/OASIcs.SOSA.2018.12. [BLP+1...

work page doi:10.4230/oasics.sosa.2018.12 2018

[8] [2007]

[MV13] Daniele Micciancio and Panagiotis Voulgaris

doi:10.1137/S0097539705447360. [MV13] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations.SIAM Journal on Computing, 42(3):1364–1391, 2013.doi:10.1137/100811970. [Nik20] Geno Nikolov. On the extreme zeros of Jacobi polynomials,

doi:10.1137/s0097539705447360 2013