Noah Stephens-Davidowitz

activity

20152019

most citedJust Take the Average! An Embarrassingly Simple

2^{n}

-Time Algorithm for SVP (and CVP)

4 citations · 6 across the 6 of their papers we have counts for

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2019★ 1 cited

Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)

Divesh Aggarwal, Huck Bennett, Alexander Golovnev +1

We show a number of fine-grained hardness results for the Closest Vector Problem in the $ℓ_{p}$ norm ( $CVP_{p}$ ), and its approximate and non-uniform variants. First, we sh…

cs.CC2017

On the Quantitative Hardness of CVP

Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz

$ \newcommand{\eps}{\varepsilon} \newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{\CVP}{\problem{CVP}} \newcommand{\SVP}{\problem{SVP}} \newcommand{\CVPP}{\problem{C…

cs.CC2015

Discrete Gaussian Sampling Reduces to CVP and SVP

Noah Stephens-Davidowitz

The discrete Gaussian $D_{L - t, s}$ is the distribution that assigns to each vector $x$ in a shifted lattice $L - t$ probability proportional to $e^{- π ∥ x ∥^{2} / s^{2}}$ . It has long be…