Near Linear Lower Bound for Dimension Reduction in L1

DOI10.1109/FOCS.2011.87zbMath1292.68080OpenAlexW2001085501MaRDI QIDQ5494973

No author found.

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)

Related Items (8)

Entropy-based bounds on dimension reduction in \(L^1\) ⋮ Dimension reduction for finite trees in \(\ell_1\) ⋮ Bounds on Dimension Reduction in the Nuclear Norm ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Unnamed Item ⋮ Unnamed Item

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