Mind the Gap? Not for SVP Hardness under ETH!

Aditya Morolia; Chuanqi Zhang; Divesh Aggarwal; Rishav Gupta

arxiv: 2504.02695 · v2 · submitted 2025-04-03 · 💻 cs.CC · cs.CR· cs.DS

Mind the Gap? Not for SVP Hardness under ETH!

Divesh Aggarwal , Rishav Gupta , Aditya Morolia , Chuanqi Zhang This is my paper

Pith reviewed 2026-05-22 21:33 UTC · model grok-4.3

classification 💻 cs.CC cs.CRcs.DS

keywords lattice problemsshortest vector problemclosest vector problemexponential time hypothesisell_p normsrandomized reductionscomputational hardness

0 comments

The pith

For any p-norm the closest vector problem has no 2 to the o of n time algorithm unless ETH is false.

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

The paper establishes ETH hardness for the approximate closest vector problem in every ell_p norm through a deterministic reduction from a gap version of MAXLIN. It then shows randomized ETH hardness for the shortest vector problem when p exceeds 2 by proving a new geometric fact about the integer lattice. This fact states that lattice vectors near half the all-ones vector outnumber short vectors near the origin by an exponential margin. The result matters because it rules out subexponential algorithms for these core lattice problems that appear in optimization, coding, and cryptography. A sympathetic reader would view the work as extending prior hardness results uniformly across norms.

Core claim

For any p in the interval from 1 to infinity there exists an explicit constant gamma greater than 1 such that the gap closest vector problem in the p-norm admits no 2 to the o of n time algorithm unless the exponential time hypothesis fails. The proof uses a direct deterministic reduction from gap MAXLIN. For the shortest vector problem when p is greater than 2 the authors give a randomized reduction from CVP that rests on a novel geometric property of the integer lattice Z to the n: the number of lattice vectors close to one-half the all-ones vector is exponentially larger than the number of short vectors near the origin. This property is established by a new inequality for the Theta series

What carries the argument

The novel geometric property of the integer lattice Z^n in the ell_p norm for p greater than 2 that the number of lattice vectors close to half the all-ones vector is exponentially larger than the number near the origin.

If this is right

CVP in any ell_p norm requires 2 to the Omega of n time under ETH for some explicit gamma greater than 1.
SVP in ell_p norms for p greater than 2 requires 2 to the Omega of n time under ETH via a randomized reduction.
Bounded distance decoding receives improved ETH hardness thresholds for every p and alpha above an explicit p-dependent value.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same geometric counting idea might be adapted to derive hardness for other lattice problems such as learning with errors in non-Euclidean norms.
If the Theta-function inequality can be strengthened it could remove the randomization from the SVP reduction.
These results tighten the known connections between CSP hardness and geometric lattice problems in high dimensions.

Load-bearing premise

The integer lattice in the p-norm for p greater than 2 has exponentially more vectors near half the all-ones vector than near the origin.

What would settle it

A counterexample showing that the count of lattice vectors near half the all-ones vector is not exponentially larger than the count near zero for some p greater than 2 or a 2 to the o of n time algorithm for SVP in such a norm would refute the central claim assuming ETH holds.

read the original abstract

We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al.\ \cite{BHIRW24}, who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $\gamma > 1$ such that $\mathsf{CVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,\gamma}$. Our main contribution is a randomized ETH hardness result for $\mathsf{SVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p \in (2, \infty)$. This result relies on a novel geometric property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm, which says that for any $p \in (2, \infty)$, the number of lattice vectors close to $\frac{1}{2}\vec{1}_n$ (in the $\ell_p$ norm) is exponentially larger than the number of short vectors (namely those close to the origin). We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from $\mathsf{CVP}_{p,\gamma}$ to $\mathsf{SVP}_{p,\gamma'}$. Finally, we also use our ideas to give some minor improvements over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p,\alpha}$ (the Bounded Distance Decoding Problem), yielding better ETH hardness results for $\mathsf{BDD}_{p,\alpha}$ for any $p \in [1, \infty)$ and $\alpha > \alpha_p^{\ddagger}$, where $\alpha_p^{\ddagger}$ is an explicit threshold depending on $p$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives ETH hardness for CVP in all l_p and randomized hardness for SVP when p>2 via a new lattice counting property, but the theta inequality is the piece that needs verification.

read the letter

This paper's main result is ETH-hardness for approximate CVP in every l_p norm, plus a randomized ETH-hardness for SVP when p > 2. The CVP part is deterministic and comes from a direct reduction from gap-MAXLIN. They build cleanly on the Bitansky et al. work to get the CVP hardness for all p in [1, infinity). That part looks like a straightforward extension and earns credit for closing the gap between CVP and SVP under ETH for p > 2. The SVP result uses a randomized reduction that samples a shift and counts on a new property: in l_p for p > 2, there are exponentially more lattice points near (1/2) times the all-ones vector than near the origin. They prove this with a fresh inequality on the Jacobi theta function. If the inequality holds with the right constants, the reduction preserves the approximation factor. The soft spot is exactly that inequality. The stress test flags it as the point where the SVP claim could fail if the exponential separation isn't strong enough or if there's a derivation slip. Since the full proof details aren't in the abstract, a referee would have to verify the theta bound carefully. The CVP hardness stands on its own, but the SVP one is tied to this new argument. This is for people who work on fine-grained complexity of lattice problems or who need conditional lower bounds for crypto assumptions. A reader who follows ETH reductions will get value from the CVP result immediately. It deserves peer review because the deterministic part is grounded and the new property is stated explicitly, even though the randomized step needs checking. I would recommend sending it to referees.

Referee Report

2 major / 1 minor

Summary. The paper proves ETH-hardness for approximate lattice problems. For any p ∈ [1, ∞) there exists explicit γ > 1 such that CVP_{p,γ} has no 2^{o(n)}-time algorithm unless ETH is false, via a deterministic reduction from gap-MAXLIN. The main result is a randomized ETH-hardness for SVP_{p,γ} when p ∈ (2, ∞), obtained by a randomized reduction from CVP that relies on a new geometric property of ℤ^n in the ℓ_p norm: the number of lattice vectors near (1/2)1_n is exponentially larger than the number near the origin. This separation is established by a new inequality on the Jacobi theta function θ_{ℤ^n,p}(z). Minor improvements to prior BDD hardness results are also given.

Significance. If the new theta-function inequality holds and supplies a sufficiently strong exponential gap, the randomized CVP-to-SVP reduction would close an open gap and yield the first ETH-hardness for SVP in ℓ_p norms for all p > 2. The deterministic CVP result is independent of this step and rests on the cited MAXLIN breakthrough. The work supplies explicit constants and a concrete geometric property that could be of independent interest.

major comments (2)

[Abstract (geometric property paragraph) and the section deriving the theta inequality] The randomized reduction from CVP_{p,γ} to SVP_{p,γ'} (p ∈ (2, ∞)) is load-bearing for the main SVP claim and rests entirely on the asserted exponential separation between the number of vectors near (1/2)1_n and near the origin. The abstract states that this separation follows from a new inequality on θ_{ℤ^n,p}(z), but the manuscript must supply the precise statement of the inequality, the range of r for which the gap holds, and a complete error analysis showing that the gap is large enough to preserve a constant γ' > 1 after randomization. Without these details the reduction cannot be verified.
[Section describing the MAXLIN-to-CVP reduction] The deterministic CVP hardness is stated to follow directly from the MAXLIN result of Bitansky et al. The manuscript should explicitly record the approximation factor γ obtained from that reduction (including any dependence on p) so that the final ETH-hardness statement for CVP_{p,γ} can be checked for consistency with the cited source.

minor comments (1)

Notation for the theta function and the precise definition of the counting radii r should be introduced once and used consistently; the abstract uses both “close to” and “≤ r” without defining the relationship.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. We address the two major comments below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

Referee: [Abstract (geometric property paragraph) and the section deriving the theta inequality] The randomized reduction from CVP_{p,γ} to SVP_{p,γ'} (p ∈ (2, ∞)) is load-bearing for the main SVP claim and rests entirely on the asserted exponential separation between the number of vectors near (1/2)1_n and near the origin. The abstract states that this separation follows from a new inequality on θ_{ℤ^n,p}(z), but the manuscript must supply the precise statement of the inequality, the range of r for which the gap holds, and a complete error analysis showing that the gap is large enough to preserve a constant γ' > 1 after randomization. Without these details the reduction cannot be verified.

Authors: We agree that the precise statement of the inequality, the applicable range of r, and a complete error analysis are required to verify that the exponential gap preserves a constant γ' > 1. In the revised manuscript we will insert the full statement of the new theta-function inequality, specify the range of r for which the separation holds, and provide the detailed error analysis showing the gap is sufficient for the randomized reduction. revision: yes
Referee: [Section describing the MAXLIN-to-CVP reduction] The deterministic CVP hardness is stated to follow directly from the MAXLIN result of Bitansky et al. The manuscript should explicitly record the approximation factor γ obtained from that reduction (including any dependence on p) so that the final ETH-hardness statement for CVP_{p,γ} can be checked for consistency with the cited source.

Authors: We thank the referee for this suggestion. We will add an explicit statement of the approximation factor γ obtained from the gap-MAXLIN reduction, including its dependence on p, so that the resulting ETH-hardness claim for CVP_{p,γ} can be directly verified against the source. revision: yes

Circularity Check

0 steps flagged

No circularity: reductions rely on external MAXLIN result and a newly proved Theta-function inequality

full rationale

The derivation chain begins with an external citation to Bitansky et al. for the 3SAT-to-MAXLIN reduction, proceeds via a deterministic reduction to CVP_p,γ (explicitly constructed in the paper), and then applies a randomized CVP-to-SVP reduction that invokes a geometric separation property of Z^n in l_p (p>2). This separation is established by a new inequality on the Jacobi theta function θ_{Z^n,p}(z) that the authors derive directly rather than fitting, assuming, or importing via self-citation. No step renames a fitted parameter as a prediction, defines a quantity in terms of the target result, or reduces the central ETH-hardness claim to a self-referential loop. The paper is therefore self-contained against external benchmarks with independent mathematical content.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the Exponential Time Hypothesis and the validity of the newly derived inequality for the Theta function used to prove the lattice vector counting property. No free parameters or invented entities are apparent from the abstract.

axioms (2)

domain assumption Exponential Time Hypothesis (ETH)
All hardness results are conditional on ETH.
standard math Standard properties of lattices, l_p norms, and the Theta function
Invoked to establish the geometric property and reductions.

pith-pipeline@v0.9.0 · 5964 in / 1601 out tokens · 53980 ms · 2026-05-22T21:33:39.781106+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from CVP_{p,γ} to SVP_{p,γ′}.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Θ_p(τ,1/2) > Θ_p(τ,0) … S_∞(p,τ) > 0.5

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.