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