2026-08-14T17:32:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7182 2024-03-06T10:40:02Z ddc:004 open_access

A Spectral Gap Precludes Low-Dimensional Embeddings Naor, Assaf Metric embeddings dimensionality reduction expander graphs nonlinear spectral gaps nearest neighbor search complex interpolation Markov type. We prove that if an n-vertex O(1)-expander embeds with average distortion D into a finite dimensional normed space X, then necessarily the dimension of X is at least n^{c/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)> c(log n)^2/D^2 of Linial, London and Rabinovich, strengthens a theorem of Matousek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Assaf Naor 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.50 urn:nbn:de:0030-drops-71822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.50 eng https://creativecommons.org/licenses/by/3.0/legalcode