NP-hardness of SVP in Euclidean Space
This resolves a long-standing open problem in computational complexity, establishing the NP-hardness of a fundamental lattice problem for all Euclidean norms.
The paper proves that the Shortest Vector Problem (SVP) in Euclidean space is NP-hard, confirming a conjecture by van Emde Boas (1981) and derandomizing Ajtai's (1998) randomness result.
van Emde Boas (1981) conjectured that computing a shortest non-zero vector of a lattice in an Euclidean space is NP-hard. In this paper, we prove that this conjecture is true and hence de-randomize the classical randomness result of Ajtai (1998). Our proof builds on the construction of Bennet-Peifert (2023) on locally dense lattices via Reed-Solomon codes, and depends crucially on the work of Deligne on the Weil conjectures for higher dimensional varieties over finite fields.