Lower bounds for local versions of dimension reductions

DOI10.1007/s00454-008-9068-8zbMath1171.46008OpenAlexW2080339044MaRDI QIDQ1017913

Gideon Schechtman, Adi Shraibman

Publication date: 13 May 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9068-8

zbMATH Keywords

dimension reductionnearest neighborsJohnson-Lindenstrauss lemma

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Distance in graphs (05C12) Special maps on metric spaces (54E40) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items (6)

Prioritized Metric Structures and Embedding ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ The NOF multiparty communication complexity of composed functions ⋮ Sets of unit vectors with small subset sums ⋮ Local embeddings of metric spaces ⋮ Communication Lower Bounds Using Directional Derivatives

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• Expander graphs and their applications
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Local embeddings of metric spaces
• Unnamed Item

This page was built for publication: Lower bounds for local versions of dimension reductions