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

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

Cited in

(7)

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

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)