Computer Science/Discrete Mathematics Seminar I

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.