Date: October 19, 2026
Title: A Cryptographic Lens on the Johnson-Lindenstrauss Lemma
Speaker: Neekon Vafa, Junior Fellow of the Harvard Society of Fellows, Harvard University
Abstract: The Johnson-Lindenstrauss (JL) lemma says that for any fixed, finite set of input points in Euclidean space, a random compressing linear map approximately preserves pairwise distances. Yet if the set of input points adaptively depends on the linear map, this guarantee no longer holds for a simple reason: every compressing linear map has a non-trivial kernel. However, more interesting phenomena arise if the input points are restricted to have fixed precision (i.e., to live on the hypergrid). In this talk, I will show that the task of finding such “violating” hypergrid points, when given the matrix as input, has an exponentially large statistical-computational gap, revealing a strong limitation of efficient algorithms. The computational lower bound is under the Learning With Errors (LWE) assumption.
I will highlight two cryptographic applications arising from this perspective on the JL lemma. First, the above hardness results directly give parameters for which the JL embedding is a robust property-preserving hash function for Euclidean distances on the hypergrid. Second, one can plant certain types of backdoors into a class of deep neural networks to generate a power asymmetry between model trainers and model users, assuming LWE. Moreover, these backdoors are statistically undetectable even given the full model descriptions (e.g., all of the weights).
This talk is based on joint works with Andrej Bogdanov, Alon Rosen, and Vinod Vaikuntanathan (STOC 2026, ICML 2026).
Bio: Neekon Vafa is a Junior Fellow of the Harvard Society of Fellows and a member of the research team at RESI. His research interests lie in theoretical computer science, particularly cryptography and its connections to statistics and AI safety. He received his PhD in mathematics from MIT, where he was advised by Vinod Vaikuntanathan and supported by an NSF Graduate Research Fellowship. He was a visiting researcher at NTT Research and more recently at the Alignment Research Center. Before MIT, he was a software engineer at Google (YouTube).