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).

PDF Access Denied

We have not been able to recognize your IP address 3.142.200.226 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

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