CS Paper Radar

Euclidean SVP is deterministically NP-hard to approximate within any constant factor

Daqing Wan

cs.CC math.NT ·submitted 2026-08-12 23:53 UTC · v2
theory

Abstract

We prove that, for every constant $ρ>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $ρ$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $ρ<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.

Comment
27 pages, major revision

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic Parameterized Inapproximability of the Shortest Vector and Minimum Distance Problems

cs.CC ·2026-11-19 ·Shuichi Hirahara, Bingkai Lin, Yuwei Liu, Kazuki Ogitsuka
theory similarity 0.73
Abstract

The Shortest Vector Problem (SVP) and the Minimum Distance Problem (MDP) are central computational problems on lattices and linear codes, respectively. For every computable real $p\ge1$ and any constant factor, we prove that the parameterized SVP in the $\ell_p$ norm, with the distance threshold as the parameter, is W[1]-hard to approximate within factor $γ$ under deterministic reductions. The same method shows that, for every finite field, the parameterized MDP is W[1]-hard to approximate within any constant factor under deterministic reductions.

0.33

One-Sided-Error Parameterized Reductions for the Minimum Distance and Shortest Vector Problems

cs.CC ·2026-08-14 ·Shuichi Hirahara, Kazuki Ogitsuka
theory similarity 0.73
Abstract · Full version of RANDOM 2026

It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reductions, Bennett, Cheraghchi, Guruswami, and Ribeiro (STOC 2023) proved parameterized hardness of approximation for these problems. We partially derandomize their reductions and present one-sided-error randomized reductions: MDP is W[1]-hard to approximate within an arbitrary constant factor under FPT many-one one-sided-error randomized reductions; For every $p \ge 1$, SVP in the $\ell_p$ norm is W[1]-hard to approximate within an arbitrary constant factor below $2^{1/p}$. We demonstrate the usefulness of one-sided-error randomized reductions by showing that they can be conditionally derandomized when the target problem has an OR function. Under a standard hardness-vs-randomness assumption, namely a plausible lower-bound assumption against nondeterministic circuits, we prove a general theorem formalizing this derandomization. Here, an OR function combines several instances into one instance that preserves their disjunction. We construct such OR functions for the relevant MDP and SVP gap problems, and thereby obtain deterministic W[1]-hardness for approximating MDP over every fixed finite field within every constant factor, and for approximating SVP in $\ell_p$ norms for every fixed integer $p$ within every factor below $2^{1/p}$. Applying the same framework to Micciancio's one-sided-error randomized reduction (ToC 2012) yields, under the same circuit lower-bound assumption, deterministic polynomial-time NP-hardness of approximating Euclidean SVP within every constant factor.

0.15

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.72
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

Faster SVP in Polynomial Space

cs.DS ·2026-09-18 ·Yansong Feng, Yiming Gao, Jiaqi Liu
similarity 0.70
Abstract

Kannan's algorithm, as analyzed by Hanrot and Stehlé in 2007, solves the exact Euclidean shortest vector problem in polynomial space and $n^{\frac{n}{2e}+o(n)}$ time. In the classical setting with polynomial space, we obtain the first improvement on this bound via a randomized algorithm that runs in $n^{\frac{n}{4e}+o(n)}$ time. The main idea is to represent a fixed shortest vector in many ways as a difference of samples, thereby enabling the low-space collision search of Lyu and Zhu (SODA 2023) to replace exhaustive enumeration in the original analysis.

0.15

Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

cs.DS cs.CR ·2026-11-05 ·Jiseung Kim, Minkyu Kim, Hyung Tae Lee
similarity 0.68
Abstract · 30 pages, 1 figure

We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of \(2L\), where \(L\) is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. For \(p\ge3\), the same framework is extended using a diagonal weighted norm computed from the current point.

0.30

Hardness of Unique Shortest Vectors and Bounded Distance Decoding

cs.CC ·2026-11-06 ·Sergei Kudria, Jason Luo
theory similarity 0.67
Abstract · v2

We prove randomized NP-hardness of the unique shortest vector problem (uSVP) at every constant uniqueness factor greater than one, and of bounded distance decoding (BDD) at every fixed positive fraction less than one half of the minimum distance, in both their threshold decision and search versions. Both results hold in every fixed $\ell_p$ norm with $1\le p<\infty$. Previous Euclidean NP-hardness results for the search versions reached uniqueness factors tending to one and decoding radii greater than the minimum distance divided by $\sqrt2$. For linear codes over every fixed finite field and each fixed ${0<ρ\le1/2}$, the decision version of BDD with radius strictly less than $ρ$ times the minimum distance is equivalent under deterministic polynomial-time reductions to satisfiability for circuits promised to have at most one satisfying input. It is therefore NP-hard under randomized polynomial-time reductions. Earlier hardness for decoding general codes applied beyond half the minimum distance. For every fixed $p>2$ and for $p=\infty$, there is a constant $ε>0$ such that, under randomized polynomial-time reductions, uSVP in the $\ell_p$ norm is NP-hard at uniqueness factor $n^ε$, and BDD in the $\ell_p$ norm is NP-hard at radius $λ_1/n^ε$, where $n$ is the lattice rank and $λ_1$ is its minimum distance.

0.18

Mathematics and Efficiency of Song's CVP Hardness Reduction

cs.CC ·2026-10-29 ·Shuhong Gao
theoryhot direction similarity 0.62
Abstract

Song (2026) proves that, for every fixed $0<ε<1$, the closest codeword problem (CCP) for binary linear codes under Hamming distance is NP-hard to approximate within $N^{1-ε}$, where $N$ is the code length, under deterministic polynomial-time many-one reductions. The code-to-lattice construction gives hardness within $N^{1/2-ε/2}$ for Euclidean CVP, with the same $N$ aslattice rank. This reaches every fixed Euclidean hardness exponent below one half. Aharonov and Regev (2005), with the constant refined by Gao (2026), place GapCVP at factor $cN^{1/2}$ in $\mathrm{NP}\cap\mathrm{coNP}$ for every fixed $c>2/(π\sqrt3)\approx0.3676$. NP-hardness at that scale would imply $\mathrm{NP}=\mathrm{coNP}$. This paper has two goals: to explain Song's theorem and its mathematics for graduate students, and to make the reduction more efficient. The reduction turns satisfiability into a system of quadratic equations and then into CCP for binary linear codes, and recovers assignments from recurrence relations of algebraic moments. We adapt the method to linear codes over any fixed finite field of characteristic $p$. A common recurrence for each block column gives a moment window $L=c_p(κ-1)+1$, where $c_p=\max\{2,p-1\}$ and $κ$ is the rank cutoff. Together with ordinary digit products and flexible sampling, this reduces interpolation degrees and output lengths. For CCP gap $N^{1-ε}$, our explicit schedule gives code length and lattice rank at most $n^{4/ε^2+O(1/ε)}$; Song's prescribed binary schedule gives $n^{8/ε^2+O(1/ε)}$. Here $n$ counts variables in a common quadratic system, equal to the number of original variables plus clauses for 3SAT. These are dimension bounds, not optimality claims or running-time exponents. The limiting hardness exponents remain Song's.

0.30

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

cs.DS cs.CCmath.CO ·2026-09-09 ·Sergei Kudria, Jason Luo, Mahbod Majid
theory similarity 0.61
Abstract · 44 pages

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

0.45