17 citations · 54 across the 12 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.CC2015★ 3 cited
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
Noah Stephens-Davidowitz
We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any , we obtain an efficient dimension-p…
cs.DS2015★ 9 cited
Solving the Closest Vector Problem in Time--- The Discrete Gaussian Strikes Again!
Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz
We give a -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on -dimensional Euclidean lattices. This improves on the previous f…
math.PR2015★ 10 cited
An Inequality for Gaussians on Lattices
Oded Regev, Noah Stephens-Davidowitz
$ \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\lat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that for any lattice $\lat \subseteq \R^n$ and vectors $\vec{x},…