SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

arXiv:2609.01469 · cs.CC, cs.CR · Submitted 2026-09-01 · Read on arXiv

cs.CC, cs.CR

Submitted: 2026-09-01

Updated: 2026-09-01

Terminology

• Shortest Vector Problem — 7× in this paper
• Embeddings — 2× in this paper · explained in 2 episodes
• Verifier — 2× in this paper · explained in 2 episodes
• Abundance — 1× in this paper · explained in 1 episode
• Annual ACM Symposium on Theory of Computing — 1× in this paper
• Trace — 1× in this paper · explained in 2 episodes
• Verification — 1× in this paper · explained in 2 episodes

Sources

• Module lattices and their shortest vectors
• Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
• Euclidean SVP is deterministically NP-hard to approximate within any constant factor
• NP-hardness of SVP in Euclidean Space

Related papers

• Parameterized Hardness of Zonotope Containment and Neural Network Verification
• Hardware-Algorithm Co-Optimization of Early-Exit Neural Networks for Multi-Core Edge Accelerators
• Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
• Strassen's support functionals coincide with the quantum functionals
• Exponential Quantum Advantage in Numbers-on-Forehead Communication
• Rational degree is polynomially related to degree