An average John theorem

We deduce from this (optimal) statement that if an $n$ –vertex expander embeds with average distortion $D \geq 1$ into $X$ , then necessarily $dim (X) \geq n^{Ω (1 ∕ D)}$ , which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound $dim (X) ≳ {(log n)}^{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

Mathematical Subject Classification 2010

Primary: 30L05

References

Publication

Received: 7 December 2016

Revised: 7 February 2020

Accepted: 11 May 2020

Published: 12 July 2021

Proposed: Yasha Eliashberg

Seconded: David M Fisher, Tobias H Colding

Authors

Assaf Naor
Department of Mathematics Princeton University Princeton, NJ United States

Volume 25, issue 4 (2021)

Assaf Naor

Abstract

Keywords

Mathematical Subject Classification 2010

References

Publication

Authors