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.DSShow all

4 papers · 1 filter

cs.DS2019

Slide Reduction, Revisited---Filling the Gaps in SVP Approximation

Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen +1

We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the f…

cs.DS2019★ 1 cited

A time-distance trade-off for GDD with preprocessing---Instantiating the DLW heuristic

Noah Stephens-Davidowitz

For $0 \leq α \leq 1/2$ , we show an algorithm that does the following. Given appropriate preprocessing $P (L)$ consisting of $N_{α} := 2^{O (n^{1 - 2 α} + l o g n)}$ vectors in som…

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.DS2016

On the Lattice Distortion Problem

Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz

We introduce and study the \emph{Lattice Distortion Problem} (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the…

Slide Reduction, Revisited---Filling the Gaps in SVP Approximation

A time-distance trade-off for GDD with preprocessing---Instantiating the DLW heuristic

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

On the Lattice Distortion Problem

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