Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-170 | 31st January 2023 04:35

The Complexity of the Shortest Vector Problem

RSS-Feed




Revision #1
Authors: Huck Bennett
Accepted on: 31st January 2023 04:35
Downloads: 0
Keywords: 


Abstract:

Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the Shortest Vector Problem (SVP).



Changes to previous version:

Minor fixes and wording changes.


Paper:

TR22-170 | 15th November 2022 01:13

The Complexity of the Shortest Vector Problem


Abstract:

Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the Shortest Vector Problem (SVP).



ISSN 1433-8092 | Imprint