PreprintCC BY 4.0arXiv
Euclidean SVP is deterministically NP-hard to approximate within any constant factor
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 ρ<√2 to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.
Related
- New Bounds for the Euclidean TSP Constant
- Euclidean Distance Optimization Within the Grassmannian
- Multicollinearity-agnostic feature screening for non-Euclidean responses: a factor adjusted approach
- Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs
- A constant-factor approximation of the Gromov-Hausdorff distance in the plane
BibTeX
@misc{wan2026euclidean,
title = {{Euclidean SVP is deterministically NP-hard to approximate within any constant factor}},
author = {Daqing Wan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.12664},
eprint = {2608.12664},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.12664},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Euclidean SVP is deterministically NP-hard to approximate within any constant factor
AU - Daqing Wan
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2608.12664
UR - https://arxiv.org/abs/2608.12664
AB - 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 ρ<√2 to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.
ER -