A spectral gap precludes low-dimensional embeddings

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (aij) ∈ Mn(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ2(A). Then for any finite-dimensional normed space (X, ⊥ · ⊥) we have (Equation presented) It follows that if an n-vertex O(1)-expander embeds with average distortion D ≧ 1 into X, then necessarily dim(X) ≳ nc/D for some universal constant c > 0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X) ≳ (log n)2/D2 of Linial, London and Rabinovich, strengthens a theorem of Matoušek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.

Original languageEnglish (US)
Title of host publication33rd International Symposium on Computational Geometry, SoCG 2017
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages501-5016
Number of pages4516
Volume77
ISBN (Electronic)9783959770385
DOIs
StatePublished - Jun 1 2017
Event33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia
Duration: Jul 4 2017Jul 7 2017

Other

Other33rd International Symposium on Computational Geometry, SoCG 2017
CountryAustralia
CityBrisbane
Period7/4/177/7/17

All Science Journal Classification (ASJC) codes

  • Software

Cite this

Naor, A. (2017). A spectral gap precludes low-dimensional embeddings. In 33rd International Symposium on Computational Geometry, SoCG 2017 (Vol. 77, pp. 501-5016). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2017.50