
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov of the University of Ottawa presents a Computer Science and Discrete Mathematics Seminar at the Institute for Advanced Study on random projections and cryptographic hashing. He starts from the 1984 Johnson-Lindenstrauss result, which shows that projecting a point set into lower dimensions roughly preserves distances as long as the set is no larger than exponential in the target dimension. Bogdanov examines what happens when the set is the n-dimensional hypergrid of bounded integer points, a case where contracting pairs of points exist in abundance yet turn out to be computationally hard to find, a gap between what is statistically true and what an algorithm can actually locate. He then applies this gap cryptographically, showing that the rounded Johnson-Lindenstrauss embedding works as a property-preserving hash function that compresses data while making it infeasible for any bounded adversary to find a pair violating the distortion bound. The talk draws on joint work with Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan.