Volume 25, issue 4 (2021)

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

Volume 25
Issue 4, 1631–2166
Issue 3, 1087–1630
Issue 2, 547–1085
Issue 1, 1–546

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

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