A spectral gap precludes low-dimensional embeddings

DOI10.4230/LIPICS.SOCG.2017.50zbMath1433.68312arXiv1611.08861OpenAlexW2964245156MaRDI QIDQ4580127

Assaf Naor

Publication date: 13 August 2018

Full work available at URL: https://arxiv.org/abs/1611.08861

zbMATH Keywords

dimensionality reductioncomplex interpolationexpander graphsnearest neighbor searchMarkov typemetric embeddingsnonlinear spectral gaps

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Stochastic matrices (15B51) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Metric embeddings as related to computational problems and algorithms (68R12)

Related Items (4)

Impossibility of almost extension ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ An average John theorem ⋮ Nonpositive curvature is not coarsely universal

This page was built for publication: A spectral gap precludes low-dimensional embeddings