Please note: This seminar will take place in DC 1304 and online.
Andrej Bogdanov, Professor
School of Electrical Engineering and Computer Science, University of Ottawa
In 1984 W. B. Johnson and J. 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. 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.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.