TCS+ Talk

We consider the question: given integers n,d > 1, and some 0 < epsilon < 1, what is the minimum value of m such that for all n-point subsets X of d-dimensional Euclidean space, there exists an embedding f from X to m-dimensional Euclidean space with distortion at most 1+epsilon? We show that for nearly the full range of interest for the parameters n, d, and epsilon, the Johnson-Lindenstrauss lemma is tight: there exists an n-point subset of d-dimensional Euclidean space such that any such f must have m in Omega(epsilon^{-2} log n).

Joint work with Kasper Green Larsen (Aarhus University).