{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:45Z","timestamp":1750306845195,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,6,8]],"date-time":"2014-06-08T00:00:00Z","timestamp":1402185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,6,8]]},"DOI":"10.1145\/2582112.2582170","type":"proceedings-article","created":{"date-parts":[[2014,5,2]],"date-time":"2014-05-02T14:01:31Z","timestamp":1399039291000},"page":"60-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Impossibility of Dimension Reduction for Doubling Subsets of \u2113p"],"prefix":"10.1145","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[{"name":"Hebrew University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lee-Ad","family":"Gottlieb","sequence":"additional","affiliation":[{"name":"Ariel University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,6,8]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"363","volume-title":"Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, SODA '08","author":"Abraham Ittai","year":"2008","unstructured":"Ittai Abraham , Yair Bartal , and Ofer Neiman . Embedding metric spaces in their intrinsic dimension . In Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, SODA '08 , pages 363 -- 372 , Philadelphia, PA, USA , 2008 . Society for Industrial and Applied Mathematics. Ittai Abraham, Yair Bartal, and Ofer Neiman. Embedding metric spaces in their intrinsic dimension. In Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, SODA '08, pages 363--372, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.72"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347170"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.87"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796498"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-7550-1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"e_1_3_2_1_10_1","volume-title":"Dimension reduction techniques for lp (1 \u2264","author":"Bartal Y.","year":"2013","unstructured":"Y. Bartal and L. Gottlieb . Dimension reduction techniques for lp (1 \u2264 p \u2264 \u221e), with applications, 2013 . Manuscript . Y. Bartal and L. Gottlieb. Dimension reduction techniques for lp (1 \u2264 p \u2264 \u221e), with applications, 2013. Manuscript."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214038"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133104"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.003"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.79"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109566"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734213.1734215"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_12"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.01.001"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.001"},{"key":"e_1_3_2_1_23_1","volume-title":"COLT","author":"Gottlieb Lee-Ad","year":"2010","unstructured":"Lee-Ad Gottlieb , Aryeh Kontorovich , and Robert Krauthgamer . Efficient classification for metric data . In COLT , 2010 . Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient classification for metric data. In COLT, 2010."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133105"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/120874242"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347148"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946308"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9359-3"},{"key":"e_1_3_2_1_31_1","first-page":"189","volume-title":"Conference in modern analysis and probability","author":"William","year":"1982","unstructured":"William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space . In Conference in modern analysis and probability ( New Haven, Conn. , 1982 ), pages 189 -- 206 . American Mathematical Society, Providence, RI, 1984. William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189--206. American Mathematical Society, Providence, RI, 1984."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281113"},{"key":"e_1_3_2_1_34_1","first-page":"798","volume-title":"SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms","author":"Krauthgamer Robert","year":"2004","unstructured":"Robert Krauthgamer and James R. Lee . Navigating nets: simple algorithms for proximity search . In SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages 798 -- 807 , Philadelphia, PA, USA , 2004 . Society for Industrial and Applied Mathematics. Robert Krauthgamer and James R. Lee. Navigating nets: simple algorithms for proximity search. In SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 798--807, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276877"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609302001200"},{"key":"e_1_3_2_1_38_1","volume-title":"A doubling subset of Lp for","author":"Lafforgue Vincent","year":"2013","unstructured":"Vincent Lafforgue and Assaf Naor . A doubling subset of Lp for p > 2 that is inherently infinite dimensional, 2013 . preprint. Vincent Lafforgue and Assaf Naor. A doubling subset of Lp for p > 2 that is inherently infinite dimensional, 2013. preprint."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012093209450"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.07.002"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806775"},{"key":"e_1_3_2_1_42_1","first-page":"745","volume-title":"Lee and Assaf Naor. Embedding the diamond graph in lp and dimension reduction in l1","author":"James","year":"2004","unstructured":"James R. Lee and Assaf Naor. Embedding the diamond graph in lp and dimension reduction in l1 . pages 745 -- 747 , 2004 . James R. Lee and Assaf Naor. Embedding the diamond graph in lp and dimension reduction in l1. pages 745--747, 2004."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993737"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1994.365733"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/581165"},{"key":"e_1_3_2_1_46_1","volume-title":"Assouad's theorem with dimension independent of the snowflaking. Revista Matematica Iberoamericana, 28(4,):1--21","author":"Naor Assaf","year":"2012","unstructured":"Assaf Naor and Ofer Neiman . Assouad's theorem with dimension independent of the snowflaking. Revista Matematica Iberoamericana, 28(4,):1--21 , 2012 . Assaf Naor and Ofer Neiman. Assouad's theorem with dimension independent of the snowflaking. Revista Matematica Iberoamericana, 28(4,):1--21, 2012."},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 11th international conference on Approximation and Online Algorithms, WAOA","author":"Neiman Ofer","year":"2013","unstructured":"Ofer Neiman . Low dimensional embedding of doubling metrics . In Proceedings of the 11th international conference on Approximation and Online Algorithms, WAOA , 2013 . Ofer Neiman. Low dimensional embedding of doubling metrics. In Proceedings of the 11th international conference on Approximation and Online Algorithms, WAOA, 2013."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513412"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780609"},{"key":"e_1_3_2_1_50_1","first-page":"1","volume-title":"Israel Journal of Mathematics","author":"Regev Oded","year":"2012","unstructured":"Oded Regev . Entropy-based bounds on dimension reduction in l 1 . Israel Journal of Mathematics , pages 1 -- 8 , 2012 . Oded Regev. Entropy-based bounds on dimension reduction in l 1. Israel Journal of Mathematics, pages 1--8, 2012."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4171\/RMI\/201"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073823"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_3_2_1_54_1","volume-title":"The Random Projection Method","author":"Vempala S. S.","year":"2004","unstructured":"S. S. Vempala . The Random Projection Method . American Mathematical Society , 2004 . S. S. Vempala. The Random Projection Method. American Mathematical Society, 2004."}],"event":{"name":"SOCG'14: Annual Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Kyoto Japan","acronym":"SOCG'14"},"container-title":["Proceedings of the thirtieth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2582112.2582170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2582112.2582170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:10Z","timestamp":1750234210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2582112.2582170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,8]]},"references-count":54,"alternative-id":["10.1145\/2582112.2582170","10.1145\/2582112"],"URL":"https:\/\/doi.org\/10.1145\/2582112.2582170","relation":{},"subject":[],"published":{"date-parts":[[2014,6,8]]},"assertion":[{"value":"2014-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}