Optimal randomized clustering for subsets of L_p when p > 2

We resolve multiple fundamental open questions about the bi-Lipschitz geometry of subsets of L_p for 2 ≤ p < ∞ via a novel multiscale and localization framework. Specifically, we prove that the separation modulus of any n-point subset of L_p is Θ_p(√log n). If that subset has doubling constant λ, then we obtain the improved bound O_p(√log λ), which is new even for the Euclidean space p = 2. We also break the longstanding O(log n) barrier for embedding every n-point subset of L_p into Euclidean space for all p > 2, as well as the longstanding O((log n)/log log n) barrier for their Lipschitz extension modulus.