(Gap/S)ETH Hardness of SVP. Aggarwal, D. & In STOC, 2018.
$\newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{§VP}{\problem{SVP}} \newcommand{\ensuremath}[1]{#1}$We prove the following quantitative hardness results for the Shortest Vector Problem in the $\ell_p$ norm ($§VP_p$), where $n$ is the rank of the input lattice. $•$ For "almost all" $p > p_0 ≈ 2.1397$, there no $2^{n/C_p}$-time algorithm for $§VP_p$ for some explicit constant $C_p > 0$ unless the (randomized) Strong Exponential Time Hypothesis (SETH) is false. $•$ For any $p > 2$, there is no $2^{o(n)}$-time algorithm for $§VP_p$ unless the (randomized) Gap-Exponential Time Hypothesis (Gap-ETH) is false. Furthermore, for each $p > 2$, there exists a constant $γ_p > 1$ such that the same result holds even for $γ_p$-approximate $§VP_p$. $•$ There is no $2^{o(n)}$-time algorithm for $§VP_p$ for any $1 ≤ p ≤ 2$ unless either (1) (non-uniform) Gap-ETH is false; or (2) there is no family of lattices with exponential kissing number in the $\ell_2$ norm. Furthermore, for each $1 ≤ p ≤ 2$, there exists a constant $γ_p > 1$ such that the same result holds even for $γ_p$-approximate $§VP_p$.
@inproceedings{ASGapETH18,
abstract = {$\newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{\SVP}{\problem{SVP}} \newcommand{\ensuremath}[1]{#1}$We prove the following quantitative hardness results for the Shortest Vector Problem in the $\ell_p$ norm ($\SVP_p$), where $n$ is the rank of the input lattice. $\bullet$ For "almost all" $p > p_0 \approx 2.1397$, there no $2^{n/C_p}$-time algorithm for $\SVP_p$ for some explicit constant $C_p > 0$ unless the (randomized) Strong Exponential Time Hypothesis (SETH) is false. $\bullet$ For any $p > 2$, there is no $2^{o(n)}$-time algorithm for $\SVP_p$ unless the (randomized) Gap-Exponential Time Hypothesis (Gap-ETH) is false. Furthermore, for each $p > 2$, there exists a constant $\gamma_p > 1$ such that the same result holds even for $\gamma_p$-approximate $\SVP_p$. $\bullet$ There is no $2^{o(n)}$-time algorithm for $\SVP_p$ for any $1 \leq p \leq 2$ unless either (1) (non-uniform) Gap-ETH is false; or (2) there is no family of lattices with exponential kissing number in the $\ell_2$ norm. Furthermore, for each $1 \leq p \leq 2$, there exists a constant $\gamma_p > 1$ such that the same result holds even for $\gamma_p$-approximate $\SVP_p$.},
}