Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
For complexity theorists studying parameterized hardness of approximation, this work provides optimal lower bounds under a weaker and more standard assumption (ETH) via a simpler reduction.
The paper proves tight lower bounds for approximating parameterized Maximum Likelihood Decoding and Nearest Codeword Problem under the Exponential Time Hypothesis (ETH), achieving n^{Ω(k)} hardness for constant-factor approximation, which was previously only known under the stronger Gap-ETH assumption.
We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis ($\mathsf{ETH}$), yields tight lower bounds for approximating the parameterized Maximum Likelihood Decoding problem ($\mathsf{MLD}$) and the parameterized Nearest Codeword Problem ($\mathsf{NCP}$) within some fixed constant factor. Our starting point is the ETH-based exponential-time hardness of $(c,s)$-Gap-$\mathsf{MAXLIN}$ established in [BHI+24]. We transform a $(c,s)$-Gap-$\mathsf{MAXLIN}$ instance into an instance of $γ$-Gap $k$-$\mathsf{MLD}$ via a novel combinatorial object that we call a cover family. We provide both a randomized construction of the required cover families and a subsequent derandomization. Prior to our work, $n^{Ω(k)}$ hardness for constant-factor approximation was only shown under the randomized Gap Exponential Time Hypothesis Gap-$\mathsf{ETH}$ [Man20], which is a much stronger assumption than $\mathsf{ETH}$. Under $\mathsf{ETH}$, the strongest known lower bound was $n^{Ω(k/\operatorname{poly} \log k)}$ due to [BKM25]. Unlike previous approaches that rely on reductions from the hardness of approximating $2$-$\mathsf{CSP}$, our reduction provides a more direct and conceptually simpler route to achieving the optimal lower bounds.