Abstract
We prove that the Minimum Distance Problem (MDP) for linear codes over every fixed finite field and parameterized by the input distance bound is W[1]-hard (under randomized reductions) to approximate within any constant factor. The W[1]-hardness of (even the exact version of) MDP for binary linear codes was a longstanding and notorious open problem in parameterized complexity that was finally resolved a few years ago (Bhattacharyya et al, JACM 2021). However, their result only applied for the binary field, and they left open (and explicitly posed) the problem for general fields.
We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices, resolving the main questions left open concerning lattices in the above JACM 2021 paper. For example, we prove that SVP in the l_p norm is W[1]-hard (under randomized reductions) to approximate within any constant factor for any fixed p>1.
(Joint work with Huck Bennett, Mahdi Cheraghchi, and João Ribeiro.)