Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HUCK BENNETT:
All reports by Author Huck Bennett:

TR22-170 | 15th November 2022
Huck Bennett

The Complexity of the Shortest Vector Problem

Revisions: 1

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 ... more >>>


TR22-156 | 15th November 2022
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms

Revisions: 2

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>>




ISSN 1433-8092 | Imprint