An average John theorem

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)1631-1717
Number of pages87
JournalGeometry and Topology
Volume25
Issue number4
DOIs
StatePublished - 2021

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'An average John theorem'. Together they form a unique fingerprint.

Cite this