Theory Seminar

Friday, November 5, 2021 - 3:00pm to 4:00pm


In Person and Virtual Presentation - ET Gates Hillman 8102 and Zoom



Optimal terminal dimensionality reduction in Euclidean space

The Johnson-Lindenstrauss lemma states that for any X a subset of R^d with |X| = n and for any epsilon, there exists a map f:X-->R^m for m = O(log n / epsilon^2) such that: for all x in X, for all y in X, (1-epsilon)|x - y|_2 <= |f(x) - f(y)|_2 <= (1+epsilon)|x - y|_2. We show that this statement can be strengthened. In particular, the above claim holds true even if "for all y in X" is replaced with "for all y in R^d". We also discuss some progress on construction of such a map f which can be computed quickly.

Based on works with Yeshwanth Cherapanamjeri, and with Shyam Narayanan.

In Person and Zoom Participation. See announcement.

Event Website:

For More Information, Contact:


Seminar Series