Theory Seminar

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.

Event Website:

http://theory.cs.cmu.edu/

For More Information, Contact:

Keywords:

Seminar Series