209 citations · 489 across the 24 of their papers we have counts for
10 papers · 1 filter
Approximate Voronoi cells for lattices, revisited
Thijs Laarhoven
We revisit the approximate Voronoi cells approach for solving the closest vector problem with preprocessing (CVPP) on high-dimensional lattices, and settle the open problem of Doul…
Evolutionary techniques in lattice sieving algorithms
Thijs Laarhoven
Lattice-based cryptography has recently emerged as a prominent candidate for secure communication in the quantum age. Its security relies on the hardness of certain lattice problem…
Polytopes, lattices, and spherical codes for the nearest neighbor problem
Thijs Laarhoven
We study locality-sensitive hash methods for the nearest neighbor problem for the angular distance, focusing on the approach of first projecting down onto a low-dimensional subspac…
Graph-based time-space trade-offs for approximate near neighbors
Thijs Laarhoven
We take a first step towards a rigorous asymptotic analysis of graph-based approaches for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the compl…
Faster tuple lattice sieving using spherical locality-sensitive filters
Thijs Laarhoven
To overcome the large memory requirement of classical lattice sieving algorithms for solving hard lattice problems, Bai-Laarhoven-Stehlé [ANTS 2016] studied tuple lattice sieving,…
Hypercube LSH for approximate near neighbors
Thijs Laarhoven
A celebrated technique for finding near neighbors for the angular distance involves using a set of \textit{random} hyperplanes to partition the space into hash regions [Charikar, S…
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…
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…
Tradeoffs for nearest neighbors on the sphere
Thijs Laarhoven
We consider tradeoffs between the query and update complexities for the (approximate) nearest neighbor problem on the sphere, extending the recent spherical filters to sparse regim…
Practical and Optimal LSH for Angular Distance
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven +2
We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optima…