#### Volume 25, issue 4 (2021)

 Recent Issues
 The Journal About the Journal Editorial Board Editorial Interests Editorial Procedure Subscriptions Submission Guidelines Submission Page Policies for Authors Ethics Statement ISSN (electronic): 1364-0380 ISSN (print): 1465-3060 Author Index To Appear Other MSP Journals
An average John theorem

### Assaf Naor

Geometry & Topology 25 (2021) 1631–1717
##### Abstract

We prove that the $\frac{1}{2}$–snowflake of any finite-dimensional normed space $X$ embeds into a Hilbert space with quadratic average distortion

$O\left(\sqrt{logdim\left(X\right)}\right).$

We deduce from this (optimal) statement that if an $n$–vertex expander embeds with average distortion $D\ge 1$ into $X\phantom{\rule{-0.17em}{0ex}}$, then necessarily $dim\left(X\right)\ge {n}^{\Omega \left(1∕D\right)}$, which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound $dim\left(X\right)\gtrsim {\left(logn\right)}^{2}∕{D}^{2}$ of Linial, London and Rabinovich (1995), strengthens a theorem of Matoušek (1996) which resolved questions of Johnson and Lindenstrauss (1982), Bourgain (1985) and Arias-de-Reyna and Rodríguez-Piazza (1992), and answers negatively a question that was posed (for algorithmic purposes) by Andoni, Nguyen, Nikolov, Razenshteyn and Waingarten (2016).

##### Keywords
metric embeddings, dimension reduction, expander graphs, nonlinear spectral gaps, Markov type
Primary: 30L05