Abstract
We prove that the 1/2 –snowflake of any finite-dimensional normed space X embeds 2 into a Hilbert space with quadratic average distortion (Formula presented) We deduce from this (optimal) statement that if an n–vertex expander embeds with average distortion D >1 into X, then necessarily dim (Formula presented), which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound dim (Formula presented) 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).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1631-1717 |
| Number of pages | 87 |
| Journal | Geometry and Topology |
| Volume | 25 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2021 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Fingerprint
Dive into the research topics of 'An average John theorem'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver