Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ({ell_{{p}}}) Norms | CU Experts

Abstract.; We prove that the minimum distance problem ([Formula: see text]) on linear codes over any fixed finite field and parameterized by the input distance bound is [Formula: see text]-hard to approximate within any constant factor. We also prove analogous results for the parameterized shortest vector problem ([Formula: see text]) on integer lattices. Specifically, we prove that the [Formula: see text] in the [Formula: see text] norm is [Formula: see text]-hard to approximate within any constant factor for any fixed [Formula: see text] and [Formula: see text]-hard to approximate within a factor approaching 2 for [Formula: see text]. (We show hardness under randomized reductions in each case.) These results answer the main questions left open (and explicitly posed) by Bhattacharyya et al. [ J. ACM, 68 (2021), 16] on the complexity of the parameterized [Formula: see text] and [Formula: see text]. For the [Formula: see text], they established similar hardness for binary linear codes and left the case of general fields open. For the [Formula: see text] in [Formula: see text] norms with [Formula: see text], they showed inapproximability within some constant factor (depending on [Formula: see text]) and left open showing such hardness for arbitrary constant factors. They also left open showing [Formula: see text]-hardness even of the exact SVP in the [Formula: see text] norm.

VIVO