我们在指数时间假设（ETH）下证明了格问题的一些新难度结果。基于Bitansky等人最近的一项突破性工作[BHIRW24]，他们给出了从$\mathsf{3SAT}$到(gap)$\mathsf{MAXLIN}$问题（一类具有有限域上线性方程组的CSP）的一个多项式时间约简，我们推导出了几个格问题的ETH难度。首先，我们证明了对于任意$p \in [1, \infty)$，存在一个明确的常数$\gamma > 1$，使得$\mathsf{CVP}_{p,\gamma}$（$\ell_p$-范数近似最近向量问题）不接受$2^{o(n)}$时间算法，除非ETH为假。我们的约简是确定性的，并通过直接从(gap)$\mathsf{MAXLIN}$到$\mathsf{CVP}_{p,\gamma}$的约简实现。接下来，我们证明了对于所有$p > 2$，$\mathsf{SVP}_{p,\gamma}$（$\ell_p$-范数近似最短向量问题）的随机化ETH难度结果。此结果依赖于整数格$\mathbb{Z}^n$在$\ell_p$范数下的一个新颖性质以及从$\mathsf{CVP}_{p,\gamma}$到$\mathsf{SVP}_{p,\gamma'}$的随机化约简。最后，我们改进了从$\mathsf{3SAT}$到$\mathsf{BDD}_{p, \alpha}$（有界距离解码问题）的先前约简，得到了对于任何$p \in [1, \infty)$和$\alpha > \alpha_p^{\ddagger}$（其中$\alpha_p^{\ddagger}$是依赖于$p$的明确阈值）的$\mathsf{BDD}_{p, \alpha}$更好的ETH难度结果。此外，我们注意到先前的工作表明在代码中的间隙最小距离问题($\gamma$-$\mathsf{MDP}$)具有ETH难度。

We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al. [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 $\gamma > 1$ such that $\mathsf{CVP}_{p,\gamma}$ (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,\gamma}$. Next, we prove a randomized ETH-hardness result for $\mathsf{SVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p > 2$. This result relies on a novel property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm and a randomized reduction from $\mathsf{CVP}_{p,\gamma}$ to $\mathsf{SVP}_{p,\gamma'}$. Finally, we improve over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p, \alpha}$ (the Bounded Distance Decoding problem), yielding better ETH-hardness results for $\mathsf{BDD}_{p, \alpha}$ for any $p \in [1, \infty)$ and $\alpha > \alpha_p^{\ddagger}$, where $\alpha_p^{\ddagger}$ is an explicit threshold depending on $p$. We additionally observe that prior work implies ETH hardness for the gap minimum distance problem ($\gamma$-$\mathsf{MDP}$) in codes.