Hardness of Unique Shortest Vectors and Bounded Distance Decoding
cs.CC
Submitted: 2026-11-06
Updated: 2026-11-09
Terminology
Sources
- Improved hardness results for unique shortest vector problem
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
- Hardness of Bounded Distance Decoding on Lattices in $\ell_p$ Norms
- Parameterized Intractability of Even Set and Shortest Vector Problem
- Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
- On the Closest Vector Problem with a Distance Guarantee
- Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
- Polynomial-Factor Deterministic NP-Hardness for SVP in Every p Norm with p>2
- SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
- Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$
- Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
- NP-hardness of SVP in Euclidean Space
- Euclidean SVP is deterministically NP-hard to approximate within any constant factor
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?