All reports by Author Huck Bennett:

__
TR22-170
| 15th November 2022
__

Huck Bennett#### The Complexity of the Shortest Vector Problem

Revisions: 1

__
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: 1

Huck Bennett

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

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

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