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 2019Show 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.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…