{"id":"bab92bf7-7636-4ba4-91e9-1d3f364e0e68","arxiv_id":"2608.02478","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A new worst-case algorithm solves the shortest vector problem in 2^{0.6039n+o(n)} classical and 2^{0.5411n+o(n)} quantum time with 2^{n/2+o(n)} space, improving the previous 2^{n+o(n)} bound.","lead":"The paper gives a faster provable algorithm for the shortest vector problem in lattices, running in about 2^{0.604n} time classically and 2^{0.541n} time quantumly for n-dimensional lattices, improving the previous 2^n bound. It works by examining the curvature (Hessian) of a periodic Gaussian at candidate midpoints, which can reveal the direction of the shortest vector.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Every recovery step relies on an unverified parameter calculation for the external BDD oracle ([1, Thm 56] as used in Thm 2.4); if φ(L)/λ1(L) is not Ω(n^{-1/4}) or the oracle's preprocessing exceeds 2^{n/2+o(n)}, all variants collapse.","rationale":"Agree with reader: the BDD oracle is load-bearing and structurally separate from the Hessian construction. The paper's Theorem 2.4 is a compressed application of an external theorem, and the manuscript itself points to a missing verification artifact ('an asymptotic calculation gives...'). The final exponents also rest on parameter choices (r,R,χ) whose inequalities are asserted without a script; but those are only quantitative — a slight violation would change the constants (e.g., using the simpler g bound gives 2^{0.60404n}), not the qualitative improvement. In contrast, a failure of the BDD parameter calculation would invalidate the recovery step in every variant, so it is the most load-bearing concern. The requested check is concrete and can be done by a researcher with access to [1]. If the calculation checks out, the paper's conditional status should remain; if it fails, the central claim is unsupported.","tokens_in":36152,"tokens_out":17378,"duration_ms":394034,"concrete_test":"Independently re-derive Theorem 2.4 from the statement of [1, Thm 56]: with ε=exp(-√n), compute φ(L)/λ1(L) using the quoted inequality and verify it is ≥ n^{-1/3} for all sufficiently large n; verify that the preprocessing consists solely of DGS samples (Thm 2.7) and that the query time m·poly(n)=2^{o(n)} is correct. Also check whether [1, Thm 56] imposes any additional condition on L (e.g., λ1(L) ≥ 2^{-O(n)} or a bound on the covering radius) that is not guaranteed by the reduction. If any step fails, the recovery lemmas are unsupported and the main theorem collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every recovery step (Lemmas 3.6, 5.7, 6.9) ends with an n^{-1/3}-BDD query solved by Theorem 2.4, which is not derived in this paper. The proof of Theorem 2.4 is a three-line argument: plug ε=exp(-√n) into [1, Thm 56], assert φ(L)/λ1(L)=Ω(n^{-1/4}) from the inequality λ1(L)ηε(L*)≤√(ln((1+ε)/ε)/π)+√(n/(2π)), and claim preprocessing is 'only the discrete Gaussian samples'. This is the single bridge from an approximate eigenvector to an actual shortest vector. If the parameter calculation is wrong — e.g., the product bound is used in the wrong direction, a constant is dropped, or [1, Thm 56] actually requires a stronger precondition such as a lower bound on λ1(L) or a bound on the dual covering radius — then the BDD radius may be below n^{-1/3}λ, or the 'preprocessing' may require more than 2^{n/2+o(n)} time/space. The rest of the paper's Hessian construction does not compensate: without a working oracle at the stated radius and cost, the final query cannot return a shortest vector. The paper's own AI-use disclosure admits that remaining errors are likely human, which further underscores the need to verify this external-tooling assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes randomized classical and quantum algorithms for Search-SVP with claimed running times 2^{0.603867n+o(n)} classically and 2^{0.54106n+o(n)} quantumly, both using 2^{0.5n+o(n)} space. The central idea is to use the Hessian of the periodic Gaussian at midpoints of parity classes: for a shortest vector v, the Hessian at v/2 has a top eigenvector close to v, and this direction can be turned into a shortest vector by a preprocessing bounded-distance-decoding oracle. The paper develops a sequence of algorithms — direct parity-class enumeration, Walsh-Hadamard batching, random affine cosets of the dual lattice, importance sampling from a wider Gaussian, sparsification, and quantum minimum finding — to optimize the exponent.","tokens_in":36508,"tokens_out":9277,"duration_ms":81408,"significance":"If correct, this is a major advance: it would improve the previous worst-case 2^{n+o(n)} time/space bound and give a substantial quantum speedup, while introducing techniques (random-coset Hessians, importance sampling, sparsification for quantum search) that may be of independent interest. The proof skeleton is detailed and internally coherent; most lemmas are given with proofs, and the use of the true parity class versus wrong-class suppression is a genuine spectral-signature argument, not a circular fitting of the target vector. The main obstacles are the heavy reliance on the external preprocessing BDD theorem, whose application is only sketched, and several load-bearing numerical inequalities that are asserted without verification artifacts. These are fixable in principle but must be resolved before the central claim is established.","major_comments":[{"comment":"This theorem is the bridge from the Hessian eigenvector to an actual shortest vector and is used in every recovery step (Lemmas 3.6, 5.7, 6.9). The proof is a three-line invocation of [1, Theorem 56]. It does not state the exact hypotheses of the cited theorem, does not derive the claimed phi(L)/lambda1(L) = Omega(n^{-1/4}) bound from the displayed inequality, and does not justify that the preprocessing cost is dominated by 2^{n/2+o(n)} DGS sampling with 2^{o(n)} advice. Please supply a complete derivation. Any hidden condition on the dual lattice or on the preprocessing model would invalidate all three recovery lemmas.","section":"Section 2.1, Theorem 2.4"},{"comment":"The proof of Lemma 6.4 relies on the inequality sup_{x>=sqrt(3)} [BKL(arccos(1-2/x^2)) - r(x^2-1)] < -1/10, asserted to follow by 'standard calculus'. No derivative computation, interval bound, or code is provided. This inequality forces the 2^{-Omega(n)} error term in Lemma 6.4; without it, Lemma 6.9's recovery step has no spectral separation. This is load-bearing and must be verified rigorously, e.g., with interval arithmetic.","section":"Section 6.1, Eq. (25)"},{"comment":"The parameters r=0.2222355, R=0.400613, chi=0.3961331 are claimed to satisfy all lemma conditions and Eq. (30) by 'direct numerical calculation'. In particular, Lemma 6.6 requires chi < g2(R), but g2 is defined via a supremum in Eq. (24) and no value or interval proof is given. The final classical exponent 0.603867 is the maximum in Eq. (30); it has very little slack, so any small numerical error changes the theorem. Please provide a verified computation for Eq. (25), Eq. (30), and the condition chi < g2(R).","section":"Section 6.5, Eq. (30) and Lemma 6.6"},{"comment":"The quantum claim is argued in one paragraph. It requires a coherent oracle implementing the sparsified estimator, Walsh-Hadamard transforms, eigenvector computations, and BDD queries with only 2^{o(n)} overhead, plus QRAM of size 2^{0.36036n}. The paper does not describe the reversible implementation, and it does not verify that the quantum parameters r=0.180182, R=0.340429, chi=0.278262 satisfy all inequalities used by Lemmas 6.6, 6.8, and 6.9 and the quantum analogue of Eq. (30). Since the quantum exponent is a central advertised result, these details are needed.","section":"Section 6.8"}],"minor_comments":[{"comment":"'20.6039n' and '20.5411n' should be '2^{0.6039n}' and '2^{0.5411n}' with proper superscripts.","section":"Title/Abstract"},{"comment":"The sentence 'The time exponent is 0.60387 as in Eq. (30)' should explicitly display the three terms in the maximum, since the reader needs to see how 1/2, iota+2r, and 1-chi combine.","section":"Section 6.5"},{"comment":"The time bound contains a stray parenthesis: '2^{max{1/2,chi+2t}+o(1))n' should be '2^{(max{1/2,chi+2t}+o(1))n}'.","section":"Lemma 5.4"},{"comment":"The abort threshold is n^8 2^{2rn} tuples, while Lemma 6.13 gives an O(n^7 2^{2rn}) bound. This is harmless but should be made consistent for clarity.","section":"Algorithm 5 / Lemma 6.13"}],"recommendation":"major_revision","confidential_remarks":"The AI-use disclosure is not by itself a reason for rejection, but it makes the absence of verification artifacts for the numerical inequalities harder to overlook. The two main risks are the external BDD oracle in Theorem 2.4 and the unverified parameter checks; if the author provides a complete proof of Theorem 2.4 and a machine-checkable certificate for Eq. (25), Eq. (30), the g2(R) condition, and the quantum parameter balance, I would support acceptance. As it stands, the central claim is defensible but not yet fully established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first worst-case SVP algorithm I know that breaks 2^{n+o(n)} with 2^{n/2+o(n)} space, and the mechanism is not a repackaging of ADRS. The midpoint-Hessian idea—v/2 is close to an eigenvector of the Hessian of the periodic Gaussian, and the parity-class search—is genuinely new, and the random-coset + importance-sampling + sparsification chain is an honest construction, not a trick. The paper reads like a real algorithms paper: lemmas have proofs, parameters are explicit, and the failure modes (wrong class, wrong coset) are analyzed with exponential bounds rather than hand-waved.\n\nOn the central math, I did not find a load-bearing error. The derivation of the spectral gap via Lemmas 3.4/6.4 uses standard shell bounds, and the parity-class decomposition is coherent. The reduction to n^{-1/3}-BDD is legitimate, and the asymptotic calculation in Theorem 2.4 goes in the right direction: with ε=exp(-√n), λ1 ηε ≤ sqrt(ln((1+ε)/ε)/π)+sqrt(n/2π) ≈ sqrt(n/2π), so φ/λ1 is Ω(n^{-1/4}), which is above n^{-1/3}. I would not call that a flaw; I would call it the single most important thing to check.\n\nSoft spots, in proportion: (1) The final exponents rely on several numerical inequalities that are asserted by direct calculation (Eq. (25), Eq. (30), the quantum parameter values) with no verification artifact. Some constants are close enough that an off-by-one in the exponent would matter. This is a publishable-as-conditional issue, not a showstopper. (2) Theorem 2.4 is external and proved in three lines; every recovery lemma (3.6, 5.7, 6.9) ends there. Again, plausible, but I want a referee to re-derive it against [1, Thm 56]. (3) The quantum improved section is compressed: 'can be done reversibly' needs more detail for the coherent oracle. The rest of the quantum algorithm is standard min-finding.\n\nOne more thing: the remark that using the simpler bound g instead of g2 still gives 2^{0.60404n} is reassuring; the refined lemma is not a fragile dependency.\n\nWho gets value: lattice algorithms and post-quantum cryptanalysis people. The paper deserves a serious referee. My recommendation: send it, but ask for scripts for the numerical inequalities, an expanded proof of the reversible oracle, and an independent check of the BDD parameter calculation.","headline":"A credible new SVP exponent below 2^n built around midpoint Hessians; the architecture is clever and largely self-contained, but the final 0.6039n rests on numerical inequalities and a three-line external BDD parameter check that should be machine-verified before anyone builds a conference talk on it.","tokens_in":37043,"tokens_out":4915,"would_cite":true,"duration_ms":45505,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W20","11H06"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives classical and quantum algorithms that solve the Shortest Vector Problem (SVP) in time 2^{0.6039n} and 2^{0.5411n}, respectively, with space 2^{0.5n}, improving the previous best 2^{n+o(n)} bound.","keywords":["Shortest Vector Problem","lattice algorithms","Hessian","periodic Gaussian","discrete Gaussian sampling","bounded distance decoding","quantum algorithm","Walsh-Hadamard transform"],"falsifier":"Test the claimed BDD preprocessing bound by attempting to instantiate Theorem 2.4 with ε = exp(-√n) on a concrete lattice family and measuring the actual φ(L)/λ₁(L) ratio and preprocessing cost. Alternatively, redo the asymptotic analysis of the formula φ(L)/λ₁(L) = Ω(n^{-1/4}) and check whether the numerical constants used for r, R, χ satisfy all inequalities — any violation of the condition χ < 1/2 + g(r) or the exponent bound 1/2 + ι(r,R)+2r < 0.603867 would invalidate the theorem.","tokens_in":35938,"feed_emoji":"🔢","tokens_out":1864,"duration_ms":20305,"temperature":0.7,"pith_summary":"The paper claims to solve the exact Shortest Vector Problem (SVP) — finding the nonzero lattice vector of minimum length — in exponential time 2^{0.6039n} classically and 2^{0.5411n} quantumly, using only 2^{0.5n} space. The central idea is that at the midpoint of a shortest vector, the Hessian (second-derivative matrix) of a certain periodic Gaussian function has a top eigenvector pointing almost exactly along that shortest vector. The algorithm locates the correct parity class, estimates this Hessian from discrete Gaussian samples, and extracts the vector using a bounded-distance-decoding (BDD) oracle. A chain of optimizations — batching with Walsh-Hadamard transforms, random affine coset conditioning, importance sampling, sparsification, and quantum minimum finding — reduces the search cost from 2^{n} down to the claimed exponents. If correct, this breaks a long-standing 2^{n+o(n)} worst-case barrier for provable SVP algorithms.","feed_headline":"SVP solver breaks 2^n barrier at 2^{0.6039n}","feed_subtitle":"Midpoint Hessian fingerprints a shortest vector, trimming the worst-case exponent for lattice shortest vectors.","key_machinery":"The Hessian of the periodic Gaussian function F_s(z) := ρ_s(L+z)/ρ_s(L) evaluated at half a shortest vector. At the midpoint, the Hessian plus a scalar identity term is nearly rank-one with the dominant eigenvector pointing along the shortest vector v. This spectral fingerprint is extracted by estimating G from discrete Gaussian samples using the identity G = -4π² E[XXᵀ (-1)^{u·(BᵀX mod 2)}], and the direction is then fed to a preprocessing BDD oracle to recover v. The search over the 2ⁿ parity classes is compressed via fast Walsh-Hadamard transforms, random sublattice cosets, importance sampling, and quantum minimum finding.","core_discovery":"For any n-dimensional lattice L with shortest vector v, at the midpoint v/2 the Hessian G = ∇²F_s(v/2) of the periodic Gaussian function has the property that G + aI is close to a scalar multiple of vvᵀ, so its largest eigenvector is inversely-polynomially close to v/‖v‖. Using this directional information, a preprocessing BDD oracle recovers v exactly. The paper develops a randomized sieve over parity classes in L/2L, estimating each Hessian by averaging samples from the dual-lattice discrete Gaussian, and uses several structural optimization techniques to achieve the claimed time and space bounds.","pith_inferences":["A careful reader might suspect that the n^{-1/3}-BDD oracle invoked from the preprocessing result is the real bottleneck; the paper's claimed complexity relies on a numerical asymptotic for φ(L)/λ₁(L). If a better direct recovery from the Hessian eigenvector (without BDD) could be found, the exponent might drop further.","The optimization techniques — especially importance-sampled Hessian estimation with variable weights — could find use in other high-dimensional statistical estimation problems where sampling from a narrow Gaussian is costly but wide-Gaussian sampling is cheap.","The OpenAI sphere-packing improvement mentioned in Remark 1.2 suggests that the constants here are not final; the same framework would give 2^{0.6022n} classical and 2^{0.5393n} quantum if that improved bound is verified.","The paper's reliance on a constant that balances several exponential terms (r, R, χ) suggests that fine-tuning these parameters with more precise bounds on the Kabatiansky–Levenshtein constant could shave further small amounts off the exponent."],"forward_implications":["If correct, these algorithms provide the first proven worst-case SVP solver with sub-2^{n} time, beating the 2^{n+o(n)} bound that stood since 2015.","The quantum version gives the best known worst-case SVP quantum time at 2^{0.5411n}, strengthening the case for post-quantum lattice hardness assumptions.","The methodological toolkit — Hessian midpoint analysis, random sublattice cosets, and importance-sampled Hessian estimation — likely applies to other lattice problems such as CVP and BDD.","The parsimonious 2^{0.5n} space requirement makes these algorithms more realistic candidates for practical implementation on moderate dimensions.","The paper shows that the rate-limiting step is the BDD preprocessing, so further improvements in parameterized BDD directly reduce the SVP exponent."],"fun_headline_variants":["SVP in 2^{0.6039n} via Hessian midpoint","Hessian midpoint breaks 2^n barrier for SVP","Midpoint Hessian recovers shortest vector in 2^{0.6039n}","SVP solver uses Hessian at v/2 to hit 2^{0.6039n}"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire recovery step depends on an external preprocessing bounded-distance-decoding oracle that can solve n^{-1/3}-BDD in 2^{o(n)} query time after 2^{n/2+o(n)} preprocessing; if that oracle's preprocessing is slower, the BDD radius is smaller than claimed, or the asymptotic φ(L)/λ₁(L) = Ω(n^{-1/4}) calculation is off, the algorithm collapses.","fun_headline_variants_meta":{"raw":{"variants":["SVP in 2^{0.6039n} via Hessian midpoint","Hessian midpoint breaks 2^n barrier for SVP","Midpoint Hessian recovers shortest vector in 2^{0.6039n}","SVP solver uses Hessian at v/2 to hit 2^{0.6039n}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000759,"raw_usage":{"total_tokens":3223,"prompt_tokens":772,"completion_tokens":2451,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":516,"completion_tokens_details":{"reasoning_tokens":2362}},"tokens_in":516,"tokens_out":2451,"duration_ms":17542,"temperature":1.0,"reasoning_tokens":2362,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T06:31:23.514296+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the claimed BDD preprocessing bound by attempting to instantiate Theorem 2.4 with ε = exp(-√n) on a concrete lattice family and measuring the actual φ(L)/λ₁(L) ratio and preprocessing cost. Alternatively, redo the asymptotic analysis of the formula φ(L)/λ₁(L) = Ω(n^{-1/4}) and check whether the numerical constants used for r, R, χ satisfy all inequalities — any violation of the condition χ < 1/2 + g(r) or the exponent bound 1/2 + ι(r,R)+2r < 0.603867 would invalidate the theorem.","supporting_citations":[],"review_version":2}