We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (ETH), yields tight lower bounds for approximating the parameterized Maximum Likelihood Decoding problem (MLD) and the parameterized Nearest Codeword Problem (NCP) within some fixed constant factor. Our starting point is the ETH-based exponential-time hardness of (c, s)-Gap MAXLIN established in [Nir Bitansky et al., 2024]. We transform a (c, s)-Gap MAXLIN instance into an instance of γ-Gap k-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-ETH [Pasin Manurangsi, 2020], which is a much stronger assumption than ETH. Under ETH, the strongest known lower bound was n^{Ω(k/poly log k)} due to [Mitali Bafna et al., 2025]. Unlike previous approaches that rely on reductions from the hardness of approximating 2-CSP, our reduction provides a more direct and conceptually simpler route to achieving the optimal lower bounds.

We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al.\ \cite{BHIRW24}, who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $γ> 1$ such that $\mathsf{CVP}_{p,γ}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,γ}$. Our main contribution is a randomized ETH hardness result for $\mathsf{SVP}_{p,γ}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p \in (2, \infty)$. This result relies on a novel geometric property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm, which says that for any $p \in (2, \infty)$, the number of lattice vectors close to $\frac{1}{2}\vec{1}_n$ (in the $\ell_p$ norm) is exponentially larger than the number of short vectors (namely those close to the origin). We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from $\mathsf{CVP}_{p,γ}$ to $\mathsf{SVP}_{p,γ'}$. Finally, we also use our ideas to give some minor improvements over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p,α}$ (the Bounded Distance Decoding Problem), yielding better ETH hardness results for $\mathsf{BDD}_{p,α}$ for any $p \in [1, \infty)$ and $α> α_p^{\ddagger}$, where $α_p^{\ddagger}$ is an explicit threshold depending on $p$.