Volume 25, issue 4 (2021)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 28
Issue 3, 1005–1499
Issue 2, 497–1003
Issue 1, 1–496

Volume 27, 9 issues

Volume 26, 8 issues

Volume 25, 7 issues

Volume 24, 7 issues

Volume 23, 7 issues

Volume 22, 7 issues

Volume 21, 6 issues

Volume 20, 6 issues

Volume 19, 6 issues

Volume 18, 5 issues

Volume 17, 5 issues

Volume 16, 4 issues

Volume 15, 4 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 5 issues

Volume 11, 4 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 3 issues

Volume 7, 2 issues

Volume 6, 2 issues

Volume 5, 2 issues

Volume 4, 1 issue

Volume 3, 1 issue

Volume 2, 1 issue

Volume 1, 1 issue

The Journal
About the Journal
Editorial Board
Editorial Procedure
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
ISSN (electronic): 1364-0380
ISSN (print): 1465-3060
Author Index
To Appear
Other MSP Journals
This article is available for purchase or by subscription. See below.
An average John theorem

Assaf Naor

Geometry & Topology 25 (2021) 1631–1717

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

O(log dim (X)).

We deduce from this (optimal) statement that if an n–vertex expander embeds with average distortion D 1 into X, then necessarily dim(X) nΩ(1D), which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound dim(X) (logn)2D2 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 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-recom­mendation 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:

metric embeddings, dimension reduction, expander graphs, nonlinear spectral gaps, Markov type
Mathematical Subject Classification 2010
Primary: 30L05
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
Assaf Naor
Department of Mathematics
Princeton University
Princeton, NJ
United States