Divesh Aggarwal

activity

20112026

most citedQuantum attacks on Bitcoin, and how to protect against them

225 citations · 278 across the 25 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.DS2020

A $2^{n /2}$ -Time Algorithm for $n$ -SVP and $n$ -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP

Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz

We show a $2^{n /2 + o (n)}$ -time algorithm that finds a (non-zero) vector in a lattice $L \subset R^{n}$ with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathca…

cs.CC2020★ 2 cited

A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices

Divesh Aggarwal, Eldon Chung

Blömer and Seifert showed that $SIVP_{2}$ is NP-hard to approximate by giving a reduction from $CVP_{2}$ to $SIVP_{2}$ for constant approximation factors as lo…

cs.DS2020

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable c…

A 2n/2-Time Algorithm for n​-SVP and n​-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP

A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

A $2^{n /2}$ -Time Algorithm for $n$ -SVP and $n$ -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP