← 研踪 PaperTrailarXiv:2611.26273 · v1
Deterministic Parameterized Inapproximability of the Shortest Vector and Minimum Distance Problems
首次提交 2026-11-19 23:40
版本更新 2026-11-19 23:40
雷达观测 2026-11-20 14:52
摘要
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 and any constant factor, we prove that the parameterized SVP in the 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 23:40 · 最新观测版本
Deterministic Parameterized Inapproximability of the Shortest Vector and Minimum Distance Problems
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 and any constant factor, we prove that the parameterized SVP in the 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.
查看此版本解读 →查看此版本原文 ↗