209 citations · 489 across the 24 of their papers we have counts for
30 papers
Dual deconvolution multifocal fluorescence response matrix microscopy for aberration-free high-throughput super-resolution imaging
Sumin Lim, Sanghyeon Park, Tran Thinh Le +3
Fluorescence response matrix imaging enables separate computational correction of excitation and emission aberrations through dual deconvolution, but single-focus acquisition requi…
Dual lattice attacks for bounded distance decoding, revisited
Thijs Laarhoven
Analyses of dual lattice attacks have often assumed that the individual scores associated with short dual vectors are mutually independent. Laarhoven-Walter used this heuristic to…
Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time
Emmanouil Doulgerakis, Thijs Laarhoven
In an attempt to close the gap between the best provable and heuristic algorithms for hard lattice problems, such as the shortest (SVP) and closest vector problem (CVP), we analyze…
Spherical statistics and phase transitions in high-dimensional lattices
Thijs Laarhoven
We study the spherical statistics of all the points in a thin shell of a high-dimensional random lattice. The exact relations between lattice points make it unclear when prediction…
A lattice family with kissing numbers
Thijs Laarhoven, Scott Duke Kominers
For all prime powers , we construct lattices with kissing numbers \[ τ(\mathcal{L}_q)\geq \left(\frac{1}{2πe^2}+o(1)\right)\sqrt{q}\,e^…
A Note on Sphere Packing Bounds for Tuple Lattice Sieving
Thijs Laarhoven
A finite set of unit vectors is -irreducible if every signed sum of between two and distinct elements has norm greater than one. Let be the maximal asymptoti…
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…
Nearest neighbor decoding for Tardos fingerprinting codes
Thijs Laarhoven
Over the past decade, various improvements have been made to Tardos' collusion-resistant fingerprinting scheme [Tardos, STOC 2003], ultimately resulting in a good understanding of…
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…
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…
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…
Optimal sequential fingerprinting: Wald vs. Tardos
Thijs Laarhoven
We study sequential collusion-resistant fingerprinting, where the fingerprinting code is generated in advance but accusations may be made between rounds, and show that in this sett…
Asymptotics of Fingerprinting and Group Testing: Capacity-Achieving Log-Likelihood Decoders
Thijs Laarhoven
We study the large-coalition asymptotics of fingerprinting and group testing, and derive explicit decoders that provably achieve capacity for many of the considered models. We do t…
Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
Thijs Laarhoven
In this work we consider the large-coalition asymptotics of various fingerprinting and group testing games, and derive explicit expressions for the capacities for each of these mod…
Capacities and Capacity-Achieving Decoders for Various Fingerprinting Games
Thijs Laarhoven
Combining an information-theoretic approach to fingerprinting with a more constructive, statistical approach, we derive new results on the fingerprinting capacities for various inf…
Efficient Probabilistic Group Testing Based on Traitor Tracing
Thijs Laarhoven
Inspired by recent results from collusion-resistant traitor tracing, we provide a framework for constructing efficient probabilistic group testing schemes. In the traditional group…
Dynamic Traitor Tracing Schemes, Revisited
Thijs Laarhoven
We revisit recent results from the area of collusion-resistant traitor tracing, and show how they can be combined and improved to obtain more efficient dynamic traitor tracing sche…