Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. Stephens-Davidowitz, N. In APPROX, 2016.
Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one [link]Paper  abstract   bibtex   46 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: 46