2026-07-26T11:14:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20250 2024-07-02T07:52:54Z ddc:004 open_access

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH Li, Shuangle Lin, Bingkai Liu, Yuwei Nearest Codeword Problem Hardness of Approximations Fine-grained Complexity Parameterized Complexity Minimum Distance Problem Shortest Vector Problem In this paper we present a new gap-creating randomized self-reduction for the parameterized Maximum Likelihood Decoding problem over 𝔽_p (k-MLD_p). The reduction takes a k-MLD_p instance with k⋅ n d-dimensional vectors as input, runs in O(d2^{O(k)}n^{1.01}) time for some computable function f, outputs a (3/2-ε)-Gap-k'-MLD_p instance for any ε > 0, where k' = O(k²log k). Using this reduction, we show that assuming the randomized Exponential Time Hypothesis (ETH), no algorithms can approximate k-MLD_p (and therefore its dual problem k-NCP_p) within factor (3/2-ε) in f(k)⋅ n^{o(√{k/log 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_p and k-MDP_p 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_p, k-CVP_p and k-SVP_p. These results improve upon the previous f(k)⋅ n^{Ω(poly log k)} lower bounds for these problems under ETH using reductions by Bhattacharyya et al. (J.ACM 2021) and Bennett et al. (STOC 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuangle Li and Bingkai Lin and Yuwei Liu 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.107 urn:nbn:de:0030-drops-202500 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.107 eng https://creativecommons.org/licenses/by/4.0/legalcode