Entropy-based bounds on dimension reduction in \(L^1\)

DOI10.1007/S11856-012-0137-6zbMath1311.68176arXiv1108.1283OpenAlexW2045745231MaRDI QIDQ375695

Oded Regev

Publication date: 31 October 2013

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

New Limits to Classical and Quantum Instance Compression ⋮ Distortion of embeddings of binary trees into diamond graphs ⋮ Bounds on Dimension Reduction in the Nuclear Norm ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$

Cites Work

• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• On the impossibility of dimension reduction in l ₁
• Elements of Information Theory
• Near Linear Lower Bound for Dimension Reduction in L1

This page was built for publication: Entropy-based bounds on dimension reduction in \(L^1\)