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 2017Show all

2 papers · 1 filter

cs.DS2017★ 4 cited

Just Take the Average! An Embarrassingly Simple $2^{n}$ -Time Algorithm for SVP (and CVP)

Divesh Aggarwal, Noah Stephens-Davidowitz

We show a $2^{n + o (n)}$ -time (and space) algorithm for the Shortest Vector Problem on lattices (SVP) that works by repeatedly running an embarrassingly simple "pair and average" sie…

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…

Just Take the Average! An Embarrassingly Simple 2n-Time Algorithm for SVP (and CVP)

On the Quantitative Hardness of CVP

Just Take the Average! An Embarrassingly Simple $2^{n}$ -Time Algorithm for SVP (and CVP)