Near Linear Lower Bound for Dimension Reduction in L1

DOI10.1109/FOCS.2011.87MaRDI QIDQ5494973zbMATH OpenOpenAlexFDO

Authors

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2011.87

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of mathematical programming (90C90)

Cited in

(9)

• Entropy-based bounds on dimension reduction in L^1
• Dimension reduction for finite trees in _1
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Bounds on Dimension Reduction in the Nuclear Norm
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• Dimension reduction for finite trees in \(\ell_1\)
• On multiplicative \(\lambda\)-approximations and some geometric applications
• Dimensionality of Hamming metrics and Rademacher type
• Quantum data sketches

This page was built for publication: Near Linear Lower Bound for Dimension Reduction in L1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494973)