Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
- LecturerProf. Andrej Bogdanov (University of Ottawa)
Host: Kai-Min Chung - Time2025-06-26 (Thu.) 10:15 ~ 12:15
- LocationAuditorium 101 at IIS new Building
Abstract
In 1984 Johnson and Lindenstrauss showed that a random projection of an arbitrary point set S into low-dimensional space is approximately distance-preserving, as long as S is of size at most exponential in the target dimension. The resulting embedding has found many uses in data science.
If S is larger than exponential, however, its points can contract arbitrarily under the projection, opening the door to adversarial attacks.
We give evidence that when S is the n-dimensional hypergrid of integral points with bounded infinity-norm, the task of finding a contracting pair of points exhibits a computational-statistical gap. In a certain parameter range, contracting pairs are abundant, but finding such a pair is computationally infeasible.
As a cryptographic application, we show that the rounded Johnson-Lindenstrauss embedding is a robust property-preserving hash function. Such hash functions h compress data while preserving distances between inputs up to some distortion factor, with the guarantee that even knowing h, no computationally bounded adversary can find a pair of points that violates the distortion bound.
The talk is based on joint work with Alon Rosen, Neekon Vafa, and Vinod Vaikutanathan.
If S is larger than exponential, however, its points can contract arbitrarily under the projection, opening the door to adversarial attacks.
We give evidence that when S is the n-dimensional hypergrid of integral points with bounded infinity-norm, the task of finding a contracting pair of points exhibits a computational-statistical gap. In a certain parameter range, contracting pairs are abundant, but finding such a pair is computationally infeasible.
As a cryptographic application, we show that the rounded Johnson-Lindenstrauss embedding is a robust property-preserving hash function. Such hash functions h compress data while preserving distances between inputs up to some distortion factor, with the guarantee that even knowing h, no computationally bounded adversary can find a pair of points that violates the distortion bound.
The talk is based on joint work with Alon Rosen, Neekon Vafa, and Vinod Vaikutanathan.