225 citations · 278 across the 25 of their papers we have counts for
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 norm (), 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…
math.MG2019
An improved constant in Banaszczyk's transference theorem
Divesh Aggarwal, Noah Stephens-Davidowitz
$ \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\lat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that \[ μ(\lat) λ_1(\lat^*) < \big( 0.1275 + o(1) \big) \cdot n \…