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
SN - 1465-3060
VL - 25
SP - 1631
EP - 1717
JO - Geometry and Topology
JF - Geometry and Topology
IS - 4
ER -