4 citations · 6 across the 6 of their papers we have counts for
8 papers
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 norm (), and its approximate and non-uniform variants. First, we sh…
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…
A time-distance trade-off for GDD with preprocessing---Instantiating the DLW heuristic
Noah Stephens-Davidowitz
For , we show an algorithm that does the following. Given appropriate preprocessing consisting of vectors in som…
Just Take the Average! An Embarrassingly Simple -Time Algorithm for SVP (and CVP)
Divesh Aggarwal, Noah Stephens-Davidowitz
We show a -time (and space) algorithm for the Shortest Vector Problem on lattices (SVP) that works by repeatedly running an embarrassingly simple "pair and average" sie…
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…
A Reverse Minkowski Theorem
Oded Regev, Noah Stephens-Davidowitz
$ \newcommand{\R}{\mathbb{R}} \newcommand{\lat}{\mathcal{L}} $We prove a conjecture due to Dadush, showing that if $\lat \subset \R^n$ is a lattice such that $\det(\lat') \ge 1$ fo…
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…
Discrete Gaussian Sampling Reduces to CVP and SVP
Noah Stephens-Davidowitz
The discrete Gaussian is the distribution that assigns to each vector in a shifted lattice probability proportional to . It has long be…