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

### Location:

In Person and Virtual Presentation - ET Gates Hillman 8102 and Zoom### Speaker:

JELANI NELSON, Professor http://people.eecs.berkeley.edu/~minilek/?_ga=2.69009492.472207941.1636140135-14...### 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.*