{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,31]],"date-time":"2026-10-31T02:20:16Z","timestamp":1793413216039,"version":"4.5.0"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>A major open problem in the field of metric embedding is the existence of dimension reduction for $n$-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the point set, and not on its cardinality. In this paper, we negate this possibility for $\\ell_p$ spaces with $p&gt;2$. In particular, we introduce an $n$-point subset of $\\ell_p$ with doubling constant $O(1)$, and demonstrate that any embedding of the set into $\\ell_p^d$ with distortion $D$ must have $D\\ge\\Omega((\\frac{\\log n}{d})^{\\frac{1}{2}-\\frac{1}{p}})$.<\/jats:p>","DOI":"10.1137\/140977655","type":"journal-article","created":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T16:01:39Z","timestamp":1437062499000},"page":"1207-1222","source":"Crossref","is-referenced-by-count":2,"title":["On the Impossibility of Dimension Reduction for Doubling Subsets of $\\ell_{p}$"],"prefix":"10.1137","volume":"29","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lee-Ad","family":"Gottlieb","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,16]]},"reference":[{"key":"atypb1","first-page":"363","author":"Abraham I.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb2","unstructured":"I. Abraham, C. Gavoille, A. V. Goldberg, and D. Malkhi,\n                      Routing in networks with low doubling dimension\n                      , in Proceedings of the 26th International Conference on Distributed Computing Systems (ICDCS), IEEE Computer Society, New York, 2006."},{"key":"atypb3","first-page":"799","author":"Ackermann M. R.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Andoni, M. S. Charikar, O. Neiman, and H. L. Nguyen,\n                      Near linear lower bound for dimension reduction in l1\n                      , in Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS '11), Washington, DC, 2011, IEEE Computer Society, New York, pp. 315-323.","DOI":"10.1109\/FOCS.2011.87"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"R. I. Arriaga and S. Vempala,\n                      An algorithmic theory of learning: Robust concepts and random projection\n                      , in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 616-623.","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-7550-1"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"atypb11","first-page":"663","author":"Bartal Y.","year":"2012","journal-title":"New York"},{"key":"atypb12","first-page":"868","author":"Bartal Y.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. Beygelzimer, S. Kakade, and J. Langford,\n                      Cover trees for nearest neighbor\n                      , in Proceedings of the 23rd International Conference on Machine Learning, 2006, pp. 97-104.","DOI":"10.1145\/1143844.1143857"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.003"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, A. Jaffe, J. R. Lee, and J. Vincent,\n                      Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), IEEE Computer Society, New York, 2008, DC, pp. 761-770.","DOI":"10.1109\/FOCS.2008.79"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"T.H. Chan and A. Gupta,\n                      Small hop-diameter sparse spanners for doubling metrics\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 70-78.","DOI":"10.1145\/1109557.1109566"},{"key":"atypb18","first-page":"57","author":"Chan T.-H.","year":"2010","journal-title":"J. ACM"},{"key":"atypb19","first-page":"551","author":"Charikar M.","year":"2002","journal-title":"Vancouver, BC, Canada"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. Cole and L.A. Gottlieb,\n                      Searching dynamic point sets in spaces with bounded doubling dimension\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 574-583.","DOI":"10.1145\/1132516.1132599"},{"key":"atypb21","first-page":"157","author":"Damian M.","year":"2006","journal-title":"Proceedings of OPODIS"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.01.001"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.001"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/120874242"},{"key":"atypb25","unstructured":"L.A. Gottlieb, A. Kontorovich, and R. Krauthgamer,\n                      Efficient classification for metric data\n                      , in Proceedings of COLT, 2010."},{"key":"atypb26","first-page":"888","author":"Gottlieb L.-A.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb27","first-page":"591","author":"Gottlieb L.-A.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb28","first-page":"534","author":"Gupta A.","year":"2003","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9359-3"},{"key":"atypb32","first-page":"189","author":"Johnson W. B.","year":"1984","journal-title":"RI"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"atypb34","first-page":"71","author":"Konjevod G.","year":"2007","journal-title":"New York"},{"key":"atypb35","first-page":"798","author":"Krauthgamer R.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"atypb37","first-page":"614","author":"Kushilevitz E.","year":"1998","journal-title":"New York"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609302001200"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10711-013-9924-4"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012093209450"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.07.002"},{"key":"atypb42","first-page":"621","author":"Lee J. R.","year":"2010","journal-title":"New York"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0473-8"},{"key":"atypb44","first-page":"765","author":"Lee J. R.","year":"2011","journal-title":"New York"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"J. Matous\u030cek,\n                      Lectures on Discrete Geometry\n                      , Springer-Verlag, New York, 2002.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb47","first-page":"1","volume":"28","author":"Naor A.","year":"2012","journal-title":"Revi. Mat. Iberoam."},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"O. Neiman,\n                      Low dimensional embedding of doubling metrics\n                      , in Proceedings of the 11th International Conference on Approximation and Online Algorithms, 2013.","DOI":"10.1007\/978-3-319-08001-7_2"},{"key":"atypb49","first-page":"94","author":"Newman I.","year":"2002","journal-title":"New York"},{"key":"atypb50","first-page":"456","volume":"2003","author":"Rabinovich Y.","journal-title":"New York"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0137-6"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.4171\/RMI\/201"},{"key":"atypb53","first-page":"41","author":"Slivkins A.","year":"2005","journal-title":"New York"},{"key":"atypb54","first-page":"281","author":"Talwar K.","year":"2004","journal-title":"New York"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"S. S. Vempala,\n                      The Random Projection Method\n                      , AMS, Providence, RI, 2004.","DOI":"10.1090\/dimacs\/065"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140977655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:33Z","timestamp":1787318253000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140977655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140977655"],"URL":"https:\/\/doi.org\/10.1137\/140977655","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}