#### Alladi Ramakrishnan Hall

#### Parameterized Inapproximability of the Minimum Distance Problem over all Fields (as well as the Shortest Vector Problem in all l_p Norms

#### Venkatesan Guruswami

##### UC Berkeley

*We prove that the Minimum Distance Problem (MDP) for linear codes over*

any 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. Specifically,

we prove, again under randomized reductions, that SVP in the l_p norm

is W[1]-hard to approximate within any constant factor for any fixed

p>1, and is W[1]-hard to approximate within a factor approaching 2 for

p=1. (Joint work with Huck Bennett, Mahdi Cheraghchi, and Joćo

Ribeiro.)

Done