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

Shuangle Li, Bingkai Lin, Yuwei Liu

In this paper we present a new gap-creating randomized self-reduction for parameterized Maximum Likelihood Decoding problem over ${\mathbb{F}}_p$ ($k$-MLD${}_p$). The reduction takes a…