209 citations · 489 across the 24 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 48 cited
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the -Approximate Near Neighbor Search problem. For the -dimensional…
cs.CR2016★ 18 cited
Sieving for closest lattice vectors (with preprocessing)
Thijs Laarhoven
Lattice-based cryptography has recently emerged as a prime candidate for efficient and secure post-quantum cryptography. The two main hard problems underlying its security are the…
cs.DS2016★ 4 cited
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
We show tight lower bounds for the entire trade-off between space and query time for the Approximate Near Neighbor search problem. Our lower bounds hold in a restricted model of co…