Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one

Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. Stephens-Davidowitz, N. In APPROX, 2016.

Paper abstract bibtex 43 downloads

We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $γ ≤ 1 + O(łog n/n)$, we obtain an efficient dimension-preserving reduction from $γ^{O(n/łog n)}$-SVP to $γ$-GapSVP and an efficient dimension-preserving reduction from $γ^{O(n)}$-CVP to $γ$-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when $γ = 1$. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction–we reduce $γ^{O(n/łog n)}$-SVP to $γ$-unique SVP, a potentially easier problem than $γ$-GapSVP.

@inproceedings{SteSearchtodecisionReductions16,
  title = {Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one},
  abstract = {We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $\gamma \leq 1 + O(\log n/n)$, we obtain an efficient dimension-preserving reduction from $\gamma^{O(n/\log n)}$-SVP to $\gamma$-GapSVP and an efficient dimension-preserving reduction from $\gamma^{O(n)}$-CVP to $\gamma$-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when $\gamma = 1$. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction--we reduce $\gamma^{O(n/\log n)}$-SVP to $\gamma$-unique SVP, a potentially easier problem than $\gamma$-GapSVP.},
  url = {http://arxiv.org/abs/1512.04138},
  booktitle = {APPROX},
  author = {{Stephens-Davidowitz}, Noah},
  year = {2016}
}

Downloads: 43

{"_id":"B3woBiK9shP3HPq4G","bibbaseid":"stephensdavidowitz-searchtodecisionreductionsforlatticeproblemswithapproximationfactorsslightlygreaterthanone-2016","downloads":43,"creationDate":"2018-05-30T22:56:10.568Z","title":"Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one","author_short":["Stephens-Davidowitz, N."],"year":2016,"bibtype":"inproceedings","biburl":"https://dl.dropbox.com/s/26018h26wgh5c2o/bibbase.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one","abstract":"We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $γ ≤ 1 + O(łog n/n)$, we obtain an efficient dimension-preserving reduction from $γ^{O(n/łog n)}$-SVP to $γ$-GapSVP and an efficient dimension-preserving reduction from $γ^{O(n)}$-CVP to $γ$-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when $γ = 1$. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction–we reduce $γ^{O(n/łog n)}$-SVP to $γ$-unique SVP, a potentially easier problem than $γ$-GapSVP.","url":"http://arxiv.org/abs/1512.04138","booktitle":"APPROX","author":[{"propositions":[],"lastnames":["Stephens-Davidowitz"],"firstnames":["Noah"],"suffixes":[]}],"year":"2016","bibtex":"@inproceedings{SteSearchtodecisionReductions16,\n title = {Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one},\n abstract = {We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $\\gamma \\leq 1 + O(\\log n/n)$, we obtain an efficient dimension-preserving reduction from $\\gamma^{O(n/\\log n)}$-SVP to $\\gamma$-GapSVP and an efficient dimension-preserving reduction from $\\gamma^{O(n)}$-CVP to $\\gamma$-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when $\\gamma = 1$. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction--we reduce $\\gamma^{O(n/\\log n)}$-SVP to $\\gamma$-unique SVP, a potentially easier problem than $\\gamma$-GapSVP.},\n url = {http://arxiv.org/abs/1512.04138},\n booktitle = {APPROX},\n author = {{Stephens-Davidowitz}, Noah},\n year = {2016}\n}\n\n","author_short":["Stephens-Davidowitz, N."],"key":"SteSearchtodecisionReductions16","id":"SteSearchtodecisionReductions16","bibbaseid":"stephensdavidowitz-searchtodecisionreductionsforlatticeproblemswithapproximationfactorsslightlygreaterthanone-2016","role":"author","urls":{"Paper":"http://arxiv.org/abs/1512.04138"},"metadata":{"authorlinks":{"stephens-davidowitz, n":"https://www.noahsd.com/"}},"downloads":43},"search_terms":["search","decision","reductions","lattice","problems","approximation","factors","slightly","greater","one","stephens-davidowitz"],"keywords":[],"authorIDs":["NsKfZS8svvuZwZEBa"],"dataSources":["j49aoDnSSLjzndmof","kxAEBDHXGfX8ATRE5","HhrFT8C8XJdJggbxX","DFNYHMG5naiXCbQWf","t7S757akkuDKXd4Lt","bNuEGB6D6ArYKZG7X","rNfpY7KpfzEnPHFDu"]}