Optimal randomized clustering for subsets of Lp when p > 2

We resolve multiple fundamental open questions about the bi-Lipschitz geometry of subsets of $L_p$ for $2 \le p \lt \infty$ via a novel multiscale and localization framework. Specifically, we prove that the separation modulus of any $n$-point subset of $L_p$ is $\Theta_p(\sqrt{\log n})$. If that subset has doubling constant $\lambda$, then we obtain the improved bound $O_p(\sqrt{\log \lambda})$, 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 \gt 2$, as well as the longstanding $O((\log n)/\log\log n)$ barrier for their Lipschitz extension modulus.