Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH

In this paper we present a new gap-creating randomized self-reduction for parameterized Maximum Likelihood Decoding problem over Fₚ (k-MLDₚ). The reduction takes a k-MLDₚ instance with k n vectors as input, runs in time f (k) n^O (1) for some computable function f, outputs a (3/2-) -Gap-k'-MLDₚ instance for any >0, where k'=O (k² k). Using this reduction, we show that assuming the randomized Exponential Time Hypothesis (ETH), no algorithms can approximate k-MLDₚ (and therefore its dual problem k-NCPₚ) within factor (3/2-) in f (k) n^o (k/ k) time for any >0. We then use reduction by Bhattacharyya, Ghoshal, Karthik and Manurangsi (ICALP 2018) to amplify the (3/2-) -gap to any constant. As a result, we show that assuming ETH, no algorithms can approximate k-NCPₚ and k-MDPₚ within -factor in f (k) n^o (k^{_) } time for some constant _>0. Combining with the gap-preserving reduction by Bennett, Cheraghchi, Guruswami and Ribeiro (STOC 2023), we also obtain similar lower bounds for k-MDPₚ, k-CVPₚ and k-SVPₚ. These results improve upon the previous f (k) n^ (poly k) lower bounds for these problems under ETH using reductions by Bhattacharyya et al. (J. ACM 2021) and Bennett et al. (STOC 2023).