TY - JOUR

T1 - An average John theorem

AU - Naor, Assaf

N1 - Funding Information:
Acknowledgements This work was supported by the Packard Foundation and the Simons Foundation. The research that is presented here was conducted under the auspices of the Simons Algorithms and Geometry (A&G) Think Tank. An extended abstract [110] announcing parts of this work appeared in the 33rd International Symposium on Computational Geometry.
Publisher Copyright:
© 2021, Mathematical Science Publishers. All rights reserved.

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85104446031&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85104446031&partnerID=8YFLogxK

U2 - 10.2140/gt.2021.25.1631

DO - 10.2140/gt.2021.25.1631

M3 - Article

AN - SCOPUS:85104446031

VL - 25

SP - 1631

EP - 1717

JO - Geometry and Topology

JF - Geometry and Topology

SN - 1465-3060

IS - 4

ER -