On the quantitative hardness of CVP. Bennett, H., Golovnev, A., & Stephens-Davidowitz, N. In FOCS, 2017. Paper Princeton talk abstract bibtex 64 downloads $ \newcommand{\eps}{ε} \newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{\CVP}{\problem{CVP}} \newcommand{§VP}{\problem{SVP}} \newcommand{\CVPP}{\problem{CVPP}} \newcommand{\ensuremath}[1]{#1} $For odd integers $p ≥ 1$ (and $p = ∞$), we show that the Closest Vector Problem in the $\ell_p$ norm ($\CVP_p$) over rank $n$ lattices cannot be solved in $2^{(1-\eps) n}$ time for any constant $\eps > 0$ unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to "almost all" values of $p ≥ 1$, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of $\CVP_2$ (i.e., $\CVP$ in the Euclidean norm), for which a $2^{n +o(n)}$-time algorithm is known. In particular, our result applies for any $p = p(n) \neq 2$ that approaches $2$ as $n \to ∞$. We also show a similar SETH-hardness result for $§VP_∞$; hardness of approximating $\CVP_p$ to within some constant factor under the so-called Gap-ETH assumption; and other quantitative hardness results for $\CVP_p$ and $\CVPP_p$ for any $1 ≤ p < ∞$ under different assumptions.
@inproceedings{BGSQuantitativeHardness17,
title = {On the quantitative hardness of {CVP}},
abstract = {$ \newcommand{\eps}{\epsilon} \newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{\CVP}{\problem{CVP}} \newcommand{\SVP}{\problem{SVP}} \newcommand{\CVPP}{\problem{CVPP}} \newcommand{\ensuremath}[1]{#1} $For odd integers $p \geq 1$ (and $p = \infty$), we show that the Closest Vector Problem in the $\ell_p$ norm ($\CVP_p$) over rank $n$ lattices cannot be solved in $2^{(1-\eps) n}$ time for any constant $\eps > 0$ unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to "almost all" values of $p \geq 1$, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of $\CVP_2$ (i.e., $\CVP$ in the Euclidean norm), for which a $2^{n +o(n)}$-time algorithm is known. In particular, our result applies for any $p = p(n) \neq 2$ that approaches $2$ as $n \to \infty$. We also show a similar SETH-hardness result for $\SVP_\infty$; hardness of approximating $\CVP_p$ to within some constant factor under the so-called Gap-ETH assumption; and other quantitative hardness results for $\CVP_p$ and $\CVPP_p$ for any $1 \leq p < \infty$ under different assumptions.},
url = {http://arxiv.org/abs/1704.03928},
booktitle = {FOCS},
author = {Bennett, Huck and Golovnev, Alexander and {Stephens-Davidowitz}, Noah},
year = {2017},
url_Princeton_Talk = {http://www.youtube.com/watch?v=sd-SMjAl0ks}
}
Downloads: 64
{"_id":"PXvXw2poH2h2hpYoa","bibbaseid":"bennett-golovnev-stephensdavidowitz-onthequantitativehardnessofcvp-2017","downloads":64,"creationDate":"2018-05-30T22:56:10.556Z","title":"On the quantitative hardness of CVP","author_short":["Bennett, H.","Golovnev, A.","Stephens-Davidowitz, N."],"year":2017,"bibtype":"inproceedings","biburl":"https://dl.dropbox.com/s/26018h26wgh5c2o/bibbase.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"On the quantitative hardness of CVP","abstract":"$ \\newcommand{\\eps}{ε} \\newcommand{\\problem}[1]{\\ensuremath{\\mathrm{#1}} } \\newcommand{\\CVP}{\\problem{CVP}} \\newcommand{§VP}{\\problem{SVP}} \\newcommand{\\CVPP}{\\problem{CVPP}} \\newcommand{\\ensuremath}[1]{#1} $For odd integers $p ≥ 1$ (and $p = ∞$), we show that the Closest Vector Problem in the $\\ell_p$ norm ($\\CVP_p$) over rank $n$ lattices cannot be solved in $2^{(1-\\eps) n}$ time for any constant $\\eps > 0$ unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to \"almost all\" values of $p ≥ 1$, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of $\\CVP_2$ (i.e., $\\CVP$ in the Euclidean norm), for which a $2^{n +o(n)}$-time algorithm is known. In particular, our result applies for any $p = p(n) \\neq 2$ that approaches $2$ as $n \\to ∞$. We also show a similar SETH-hardness result for $§VP_∞$; hardness of approximating $\\CVP_p$ to within some constant factor under the so-called Gap-ETH assumption; and other quantitative hardness results for $\\CVP_p$ and $\\CVPP_p$ for any $1 ≤ p < ∞$ under different assumptions.","url":"http://arxiv.org/abs/1704.03928","booktitle":"FOCS","author":[{"propositions":[],"lastnames":["Bennett"],"firstnames":["Huck"],"suffixes":[]},{"propositions":[],"lastnames":["Golovnev"],"firstnames":["Alexander"],"suffixes":[]},{"propositions":[],"lastnames":["Stephens-Davidowitz"],"firstnames":["Noah"],"suffixes":[]}],"year":"2017","url_princeton_talk":"http://www.youtube.com/watch?v=sd-SMjAl0ks","bibtex":"@inproceedings{BGSQuantitativeHardness17,\n title = {On the quantitative hardness of {CVP}},\n abstract = {$ \\newcommand{\\eps}{\\epsilon} \\newcommand{\\problem}[1]{\\ensuremath{\\mathrm{#1}} } \\newcommand{\\CVP}{\\problem{CVP}} \\newcommand{\\SVP}{\\problem{SVP}} \\newcommand{\\CVPP}{\\problem{CVPP}} \\newcommand{\\ensuremath}[1]{#1} $For odd integers $p \\geq 1$ (and $p = \\infty$), we show that the Closest Vector Problem in the $\\ell_p$ norm ($\\CVP_p$) over rank $n$ lattices cannot be solved in $2^{(1-\\eps) n}$ time for any constant $\\eps > 0$ unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to \"almost all\" values of $p \\geq 1$, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of $\\CVP_2$ (i.e., $\\CVP$ in the Euclidean norm), for which a $2^{n +o(n)}$-time algorithm is known. In particular, our result applies for any $p = p(n) \\neq 2$ that approaches $2$ as $n \\to \\infty$. We also show a similar SETH-hardness result for $\\SVP_\\infty$; hardness of approximating $\\CVP_p$ to within some constant factor under the so-called Gap-ETH assumption; and other quantitative hardness results for $\\CVP_p$ and $\\CVPP_p$ for any $1 \\leq p < \\infty$ under different assumptions.},\n url = {http://arxiv.org/abs/1704.03928},\n booktitle = {FOCS},\n author = {Bennett, Huck and Golovnev, Alexander and {Stephens-Davidowitz}, Noah},\n year = {2017},\n url_Princeton_Talk = {http://www.youtube.com/watch?v=sd-SMjAl0ks}\n}\n\n","author_short":["Bennett, H.","Golovnev, A.","Stephens-Davidowitz, N."],"key":"BGSQuantitativeHardness17","id":"BGSQuantitativeHardness17","bibbaseid":"bennett-golovnev-stephensdavidowitz-onthequantitativehardnessofcvp-2017","role":"author","urls":{"Paper":"http://arxiv.org/abs/1704.03928"," princeton talk":"http://www.youtube.com/watch?v=sd-SMjAl0ks"},"metadata":{"authorlinks":{"stephens-davidowitz, n":"https://www.noahsd.com/"}},"downloads":64},"search_terms":["quantitative","hardness","cvp","bennett","golovnev","stephens-davidowitz"],"keywords":[],"authorIDs":["NsKfZS8svvuZwZEBa"],"dataSources":["j49aoDnSSLjzndmof","kxAEBDHXGfX8ATRE5","HhrFT8C8XJdJggbxX","DFNYHMG5naiXCbQWf","t7S757akkuDKXd4Lt"]}