{"id":"ed8f0d8a-b509-40f5-ad41-956e18c4aa04","arxiv_id":"2608.03220","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"One discrete Gaussian sample at an arbitrary parameter can be drawn in 2^(n/2+o(n)) expected time, resolving an open question from ADRS15.","lead":"A new algorithm samples from a discrete Gaussian on any lattice at any scale in roughly 2^(n/2) time, matching the speed previously available only for large scales. It also gives faster exact nearest-vector and shortest-vector algorithms under certain distance guarantees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.6 likely overstates ADRS's running time: uniform 2^{n/2+o(n)} below smoothing contradicts the paper's own abstract, and Algorithm 2's loop over all moduli m<m* would incur slow ADRS calls.","rationale":"The reader's weakest assumption identified the ADRS imported guarantee (Definition 2.5 / Theorem 2.6) as the fragile point, but focused on independence of M. My concern is that the more damaging part of the same import is the running time below the smoothing threshold: Algorithm 2 cannot avoid calling ADRS on non-smooth superlattices because it tries every modulus m=1..J, and m* is unknown. The paper's own abstract confirms ADRS is slower below smoothing, so Theorem 2.6's uniform 2^{n/2+o(n)} time is suspect. This is load-bearing because it affects the central DGS theorem's time bound, not just the applications. The reader's numeric-constant issue in Section 6 is real (likely a typo: βLev should be 2^{cLev}, not 2·cLev), but it is secondary and easy to fix. My verdict remains CONDITIONAL pending the ADRS check; if the check shows the bound is conditional and the algorithm is not modified, the verdict would become REJECT. Agreement is partial because the reader's stated weakest assumption is related but not the decisive one.","tokens_in":25371,"tokens_out":37349,"duration_ms":374677,"concrete_test":"Open ADRS15 (full version, arXiv:1412.7994) Theorem 5.11 and verify the exact running-time statement. If the 2^{n/2+o(n)} bound is conditional on s>φ(L), then instantiate it in Algorithm 2: for m<m*, the call is below threshold and costs 2^{n+o(n)}; summing over J moduli and T repetitions yields time ≥ T·2^{n+o(n)} = 2^{n+o(n)}, contradicting Theorem 4.3. If the bound is unconditional, then ADRS already solves the open question and the paper's own abstract is inconsistent; either way, the tension must be resolved by the authors.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central time bound of Theorem 4.3 rests on Theorem 2.6, which imports ADRS15, Theorem 5.11 as guaranteeing 2^{n/2+o(n)} time for every (L,s), with only the list length M changing below the threshold φ(L)=√2 η_{1/2}(L). But the paper's own introduction states that ADRS samples 2^{n/2} Gaussians at arbitrary parameter in 2^{n+o(n)} time, and only above smoothing in 2^{n/2+o(n)} time (Section 1, Abstract). Algorithm 2 loops m=1..J and calls Algorithm 1 for every m. For m<m*, the superlattice Lz is typically not smooth at t, so s=√2t is below φ(Lz); under the actual ADRS guarantee, these calls would cost 2^{n+o(n)} each. There are O(J) such moduli and T=⌈640Jκ0⌉ repetitions per modulus, so these below-threshold calls already contribute JT·2^{n+o(n)} = 2^{n+o(n)} poly(n,β_s), breaking the claimed 2^{n/2+o(n)} bound. The proof of Theorem 4.3 asserts 'Each call costs 2^{n/2+o(n)} ... by Theorem 2.6,' but if Theorem 2.6 misstates or omits a smoothing condition, the running-time argument collapses. This is distinct from the M-independence concern: even with M independent, the time bound fails. No later section repairs this; Section 5.3 explicitly sums costs per call and absorbs J only as a polynomial factor.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":25778,"tokens_out":16022,"duration_ms":165983,"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":[{"comment":"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":"Section 2 (Theorem 2.6) and Section 4 (Algorithm 2, Theorem 4.3)"},{"comment":"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.","section":"Section 6, constants before Lemma 6.1"}],"minor_comments":[{"comment":"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":"Section 5.1, Lemma 5.3"},{"comment":"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.","section":"Section 1 and Section 2"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the quotation of ADRS15, Theorem 5.11. If that theorem indeed contains an unqualified 2^{n/2+o(n)} running-time bound for all (L,s), then the paper's main algorithm works as written; if not, Algorithm 2's loop over non-smooth moduli breaks the central time claim. This should be checked against the full ADRS version before further review. The Section 6 constant error is easy to fix but must be fixed before any of the SVP/CVP exponents are quoted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThere 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.\n\nWho 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.\n\nMy 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.","headline":"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.","tokens_in":26263,"tokens_out":5340,"would_cite":false,"duration_ms":68410,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11H06","68Q17","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["discrete Gaussian sampling","smoothing parameter","superlattice sparsification","exact shortest vector problem","exact closest vector problem","rejection sampling","Poisson summation","lattice algorithms"],"falsifier":"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}$.","tokens_in":25244,"feed_emoji":"🎲","tokens_out":14069,"duration_ms":134490,"temperature":0.7,"pith_summary":"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.","feed_headline":"One Gaussian sample at any scale in 2^{n/2} time","feed_subtitle":"Resolves the 2015 ADRS open problem and yields exact SVP in 2^{0.7315n} time and sub-2^n close-target CVP.","key_machinery":"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.","core_discovery":"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,","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the underlying sampler (Definition 2.5 and Theorem 2.6) whose list length is independent of the sample values; the entire rejection step presupposes this guarantee.","marker":"[ADRS15]"},{"why":"Supplies the lattice-sparsification construction used to pick the random superlattice kernel from the dual Gaussian mass.","marker":"[DK16]"},{"why":"Its Lemma 3 lattice-point bound underlies Lemma 6.1, which controls $\\rho_s(L)$ and fixes the exponents for the CVP and SVP applications.","marker":"[PS09]"},{"why":"Provides the Kabatiansky–Levenshtein spherical-code exponent from which the constants $\\delta$ and $c_0=0.7315$ are derived.","marker":"[KL78]"},{"why":"Supplies the one-dimensional Gaussian sampling routine used inside the Turing-machine implementation of the ADRS sampler.","marker":"[BLP+13]"},{"why":"Supplies exact normal sampling from fair random bits with lazy uniform tails, used to implement real-valued comparisons exactly.","marker":"[Kar16]"},{"why":"The prior $2^{n+o(n)}$ exact-CVP algorithm that remains the relevant baseline where the new CVP exponent reaches 1.","marker":"[ADS15]"}],"fun_headline_variants":["Discrete Gaussian at any scale in 2^{n/2} expected time","Half-exponential time for one lattice Gaussian","Solves ADRS open problem: Gaussian sampling in sqrt(2^n)","Exact SVP in 2^{0.7315n} via new Gaussian sampler","Any-parameter Gaussian in 2^{n/2+o(n)} time"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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}$.","fun_headline_variants_meta":{"raw":{"variants":["Discrete Gaussian at any scale in 2^{n/2} expected time","Half-exponential time for one lattice Gaussian","Solves ADRS open problem: Gaussian sampling in sqrt(2^n)","Exact SVP in 2^{0.7315n} via new Gaussian sampler","Any-parameter Gaussian in 2^{n/2+o(n)} time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000378,"raw_usage":{"total_tokens":1926,"prompt_tokens":899,"completion_tokens":1027,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":929}},"tokens_in":643,"tokens_out":1027,"duration_ms":11163,"temperature":1.0,"reasoning_tokens":929,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:26:02.455323+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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}$.","supporting_citations":[],"review_version":1}