1 citations · 2 across the 3 of their papers we have counts for
6 papers
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
Dimension-Preserving Reductions Between SVP and CVP in Different -Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +2
We show a number of reductions between the Shortest Vector Problem and the Closest…
A -Time Algorithm for -SVP and -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz
We show a -time algorithm that finds a (non-zero) vector in a lattice with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathca…
A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices
Divesh Aggarwal, Eldon Chung
Blömer and Seifert showed that is NP-hard to approximate by giving a reduction from to for constant approximation factors as lo…
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…
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 \…