TY - JOUR
T1 - An average John theorem
AU - Naor, Assaf
N1 - 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 -