CS Paper Radar

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

Shuichi Hirahara, Kazuki Ogitsuka

cs.CC ·submitted 2026-08-14 13:43 UTC · v1
theory

Abstract

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.

Comment
Full version of RANDOM 2026

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

Hardness of Unique Shortest Vectors and Bounded Distance Decoding

cs.CC ·2026-11-06 ·Sergei Kudria, Jason Luo
theory similarity 0.74
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

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

cs.CC math.NT ·2026-08-12 ·Daqing Wan
theory similarity 0.73
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

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

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

Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

cs.DS ·2026-09-29 ·Prashanti Anderson, Peter Manohar, Jeff Xu
similarity 0.64
Abstract · 21 pages

A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refutation, where the instances are uniformly random and thus unsatisfiable with high probability, and search, where the instances are drawn from a planted model so that they are satisfiable. While there is no formal relationship between the refutation and search variants of random CSPs, known algorithms are strikingly similar with near-identical computational thresholds. In this work, we establish a formal relationship between the known algorithms for refutation and search by showing that in either case they achieve a stronger guarantee: they output an assignment $x$ along with a certificate $π$ that the fraction of constraints satisfied by $x$ is within some small $\varepsilon$ of the optimal assignment. We call this guarantee certifiable $\varepsilon$-optimality. As an application, we design new algorithms for a model of semirandom CSPs where the instance hypergraph (or scopes) is random, but the literal negation patterns are adversarially chosen and may depend on the hypergraph. For such CSPs, we give a family of algorithms that output certifiably $\varepsilon$-optimal solutions. We additionally study such semirandom CSPs in the "strong contamination model", where an adversary is allowed to corrupt an $O(δ)$-fraction of constraints after seeing the initial CSP. For such CSPs, we give an algorithm to output a certifiably $O(δ)$-optimal solution.

0.47

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.64
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

Mathematics and Efficiency of Song's CVP Hardness Reduction

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