(Gap/S)ETH Hardness of SVP. Aggarwal, D. & Stephens-Davidowitz, N. In STOC, 2018.
(Gap/S)ETH Hardness of SVP [link]Paper  abstract   bibtex   81 downloads  
$ \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,
  title = {{(Gap/S)ETH} Hardness of {SVP}},
  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$.},
  url = {http://arxiv.org/abs/1712.00942},
  booktitle = {STOC},
  author = {Aggarwal, Divesh and {Stephens-Davidowitz}, Noah},
  year = {2018}
}
Downloads: 81
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021