1 citations · 2 across the 12 of their papers we have counts for
7 papers · 1 filter
Mind the Gap? Not for SVP Hardness under ETH!
Divesh Aggarwal, Rishav Gupta, Aditya Morolia +1
We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al.\ \cite{BHIRW24}, wh…
Lattice Based Crypto breaks in a Superposition of Spacetimes
Divesh Aggarwal, Shashwat Agrawal, Rajendra Kumar
We explore the computational implications of a superposition of spacetimes, a phenomenon hypothesized in quantum gravity theories. This was initiated by Shmueli (2024) where the au…
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-…
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal, Rajendra Kumar
Recent work [BGS17,ABGS19] has shown SETH hardness of CVP in the norm for any that is not an even integer. This result was shown by giving a Karp reduction from -SA…
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…
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…