Noah Stephens-Davidowitz

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

1 citations · 1 across the 1 of their papers we have counts for

collaborators

2 papers

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…