CS Paper Radar

Hardness of Unique Shortest Vectors and Bounded Distance Decoding

Sergei Kudria, Jason Luo

cs.CC ·submitted 2026-11-06 14:18 UTC · v2
theory

Abstract

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.

Comment
v2

Closest papers

Nearest neighbours by meaning across the whole index.

On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate

cs.CC ·2026-10-29 ·Venkata Gandikota, Vatsal Jha, S. Venkitesh
similarity 0.76
Abstract · A longer version of this manuscript has been submitted for publication

In this work, we investigate the hardness of computing minimum distance, as well as the hardness of syndrome decoding, for rank-metric codes. It is known (Gaborit and Zémor, IEEE TIT 2016) that for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$, minimum distance when $m=O(N)$ and syndrome decoding when $m=O(N^2)$ are NP-hard under randomized reductions. We obtain a derandomization of these results and a bit more. We show that for any fixed small $\varepsilon>0$, for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$ with $m=O(N^{1+\varepsilon})$, the problems of minimum distance, nearest codeword, and syndrome decoding are NP-hard under deterministic reductions. Further, we can prescribe the rate; that is, if we restrict to codes having any fixed rational rate $R\in(0,1)$, then the NP-hardness for all three problems persists. Our main technical contribution is simple, and possibly of independent interest. The reduction of Gaborit and Zémor (IEEE TIT 2016) relies on a distance-preserving embedding of a Hamming-metric code into a rank-metric code, obtained by multiplying its coordinates by a uniformly random vector. We show that we can choose an explicit vector from a slightly larger extension field.

0.18

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.74
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

Mathematics and Efficiency of Song's CVP Hardness Reduction

cs.CC ·2026-10-29 ·Shuhong Gao
theoryhot direction similarity 0.71
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

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.71
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

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.70
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

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.69
Abstract

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

0.35

Hardness and Inapproximability of the Covering Radius for LDPC Codes

cs.IT ·2026-11-17 ·Massimo Battaglioni, Fabrizio Marinelli
theory similarity 0.68
Abstract

Given a binary parity-check matrix $H$ and an integer $r$, the covering-radius decision problem asks whether every attainable syndrome can be represented by an error vector of Hamming weight at most $r$. We study this problem for sparse parity-check matrices with bounded row and column weights. Using a bounded-occurrence quantified-SAT reduction, we prove that the problem is $Π_2^{\mathrm P}$-complete for matrices with maximum row and column weight three, and remains $Π_2^{\mathrm P}$-hard under a constant multiplicative gap. Starting from Vertex Cover on 3-regular graphs, we also obtain an explicit NP-hard approximation factor under the same weight constraints. We remark that weight three is the exact threshold for hardness: if either the maximum row weight or the maximum column weight is at most two, the covering radius can be computed in polynomial time.

0.28

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

cs.CC math.NT ·2026-08-12 ·Daqing Wan
theory similarity 0.67
Abstract · 27 pages, major revision

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.

0.45