{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:25Z","timestamp":1781077645825,"version":"3.54.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"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":["J. ACM"],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:p>\n            The Johnson--Lindenstrauss lemma shows that any\n            <jats:italic>n<\/jats:italic>\n            points in Euclidean space (i.e., \u211d\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            with distances measured under the \u2113\n            <jats:sub>2<\/jats:sub>\n            norm) may be mapped down to\n            <jats:italic>O<\/jats:italic>\n            ((log\n            <jats:italic>n<\/jats:italic>\n            )\/\u03f5\n            <jats:sup>2<\/jats:sup>\n            ) dimensions such that no pairwise distance is distorted by more than a (1 + \u03f5) factor. Determining whether such dimension reduction is possible in \u2113\n            <jats:sub>1<\/jats:sub>\n            has been an intriguing open question. We show strong lower bounds for general dimension reduction in \u2113\n            <jats:sub>1<\/jats:sub>\n            . We give an explicit family of\n            <jats:italic>n<\/jats:italic>\n            points in \u2113\n            <jats:sub>1<\/jats:sub>\n            such that any embedding with constant distortion\n            <jats:italic>D<\/jats:italic>\n            requires\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(1\/\n              <jats:italic>D<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:sup>\n            dimensions. This proves that there is no analog of the Johnson--Lindenstrauss lemma for \u2113\n            <jats:sub>1<\/jats:sub>\n            ; in fact, embedding with any constant distortion requires\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03a9(1)<\/jats:sup>\n            dimensions. Further, embedding the points into \u2113\n            <jats:sub>1<\/jats:sub>\n            with (1+\u03f5) distortion requires\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u00bd\u2212\n              <jats:italic>O<\/jats:italic>\n              (\u03f5 log(1\/\u03f5))\n            <\/jats:sup>\n            dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into \u2113\n            <jats:sub>1<\/jats:sub>\n            .\n          <\/jats:p>","DOI":"10.1145\/1089023.1089026","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"766-788","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["On the impossibility of dimension reduction in l\n            <sub>1<\/sub>"],"prefix":"10.1145","volume":"52","author":[{"given":"Bo","family":"Brinkman","sequence":"first","affiliation":[{"name":"Miami University, Oxford, Ohio"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moses","family":"Charikar","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, New Jersey"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM","author":"Achlioptas D.","year":"2001","unstructured":"Achlioptas , D. 2001 . Database-friendly random projections . In Proceedings of 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM , New York. 10.1145\/375551.375608 Achlioptas, D. 2001. Database-friendly random projections. In Proceedings of 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, New York. 10.1145\/375551.375608"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM","author":"Arora S.","unstructured":"Arora , S. , and Kannan , R . 2001. Learning mixtures of arbitrary gaussians . In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM , New York, 247--257. 10.1145\/380752.380808 Arora, S., and Kannan, R. 2001. Learning mixtures of arbitrary gaussians. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, New York, 247--257. 10.1145\/380752.380808"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Arriaga R.","unstructured":"Arriaga , R. , and Vempala , S . 1999. An algorithmic theory of learning: Robust concepts and random projection . In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 616--623. Arriaga, R., and Vempala, S. 1999. An algorithmic theory of learning: Robust concepts and random projection. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 616--623."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0195-6698(13)80131-X","article-title":"Isometric embedding in lp-spaces","volume":"11","author":"Ball K.","year":"1990","unstructured":"Ball , K. 1990 . Isometric embedding in lp-spaces . Europ. J. Combinat. 11 , 305 -- 311 . Ball, K. 1990. Isometric embedding in lp-spaces. Europ. J. Combinat. 11, 305--311.","journal-title":"Europ. J. Combinat."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/BF02776078","article-title":"On Lipschitz embedding of finite metric spaces into Hilbert space","volume":"52","author":"Bourgain J.","year":"1985","unstructured":"Bourgain , J. 1985 . On Lipschitz embedding of finite metric spaces into Hilbert space . Isr. J. Math. 52 , 46 -- 52 . Bourgain, J. 1985. On Lipschitz embedding of finite metric spaces into Hilbert space. Isr. J. Math. 52, 46--52.","journal-title":"Isr. J. Math."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Charikar M.","unstructured":"Charikar , M. , and Sahai , A . 2002. Dimension reduction in the &ell;1 norm . In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 551--560. Charikar, M., and Sahai, A. 2002. Dimension reduction in the &ell;1 norm. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 551--560."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Dasgupta S.","year":"1999","unstructured":"Dasgupta , S. 1999 . Learning mixtures of Gaussians . In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 634--644. Dasgupta, S. 1999. Learning mixtures of Gaussians. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 634--644."},{"key":"e_1_2_1_9_1","volume-title":"Tech. Rep. TR-99-06","author":"Dasgupta S.","year":"1999","unstructured":"Dasgupta , S. , and Gupta , A . 1999 . An elementary proof of the Johnson--Lindenstrauss lemma. Tech. Rep. TR-99-06 , International Computer Science Institute, UC Berkeley . Dasgupta, S., and Gupta, A. 1999. An elementary proof of the Johnson--Lindenstrauss lemma. Tech. Rep. TR-99-06, International Computer Science Institute, UC Berkeley."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF02764804","article-title":"Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces","volume":"79","author":"de Reyna J. A.","year":"1992","unstructured":"de Reyna , J. A. , and Rodriguez-Piazza , L. 1992 . Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces . Isr. J. Math. 79 , 103 -- 111 . de Reyna, J. A., and Rodriguez-Piazza, L. 1992. Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces. Isr. J. Math. 79, 103--111.","journal-title":"Isr. J. Math."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Deza M. and Laurent M. 1997. Geometry of Cuts and Metrics. Springer-Verlag New York.  Deza M. and Laurent M. 1997. Geometry of Cuts and Metrics. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-04295-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","article-title":"The Johnson--Lindenstrauss lemma and the sphericity of some graphs","volume":"44","author":"Frankl P.","year":"1988","unstructured":"Frankl , P. , and Maehara , H. 1988 . The Johnson--Lindenstrauss lemma and the sphericity of some graphs . J. Combinat. Theory, Ser. B 44 , 355 -- 362 . Frankl, P., and Maehara, H. 1988. The Johnson--Lindenstrauss lemma and the sphericity of some graphs. J. Combinat. Theory, Ser. B 44, 355--362.","journal-title":"J. Combinat. Theory, Ser. B"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 9th Annual ACM\/SIAM Symposium on Discrete Algorithms. ACM","author":"Indyk P.","year":"2000","unstructured":"Indyk , P. 2000 a. Dimensionality reduction techniques for proximity problems . In Proceedings of the 9th Annual ACM\/SIAM Symposium on Discrete Algorithms. ACM , New York, 371--378. Indyk, P. 2000a. Dimensionality reduction techniques for proximity problems. In Proceedings of the 9th Annual ACM\/SIAM Symposium on Discrete Algorithms. ACM, New York, 371--378."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Indyk P.","year":"2000","unstructured":"Indyk , P. 2000 b. Stable distributions, pseudorandom generators, embeddings and data stream computation . In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 189--197. Indyk, P. 2000b. Stable distributions, pseudorandom generators, embeddings and data stream computation. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 189--197."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Indyk P.","year":"2001","unstructured":"Indyk , P. 2001 . Algorithmic applications of low-distortion embeddings . In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 10--33. Indyk, P. 2001. Algorithmic applications of low-distortion embeddings. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 10--33."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM","author":"Indyk P.","unstructured":"Indyk , P. , and Motwani , R . 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality . In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM , New York, 604--613. 10.1145\/276698.276876 Indyk, P., and Motwani, R. 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, New York, 604--613. 10.1145\/276698.276876"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","article-title":"Extensions of Lipschitz mapping into Hilbert space","volume":"26","author":"Johnson W.","year":"1984","unstructured":"Johnson , W. , and Lindenstrauss , J. 1984 . Extensions of Lipschitz mapping into Hilbert space . Contemp. Math. 26 , 189 -- 206 . Johnson, W., and Lindenstrauss, J. 1984. Extensions of Lipschitz mapping into Hilbert space. Contemp. Math. 26, 189--206.","journal-title":"Contemp. Math."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_2_1_20_1","first-page":"4","article-title":"Embedding the diamond graph in lp and dimension reduction in l1","volume":"14","author":"Lee J.","year":"2004","unstructured":"Lee , J. , and Naor , A. 2004 . Embedding the diamond graph in lp and dimension reduction in l1 . Geomet. Funct. Anal. 14 , 4 (Aug.), 745--474. Lee, J., and Naor, A. 2004. Embedding the diamond graph in lp and dimension reduction in l1. Geomet. Funct. Anal. 14, 4 (Aug.), 745--474.","journal-title":"Geomet. Funct. Anal."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Congress of Mathematicians III. 573--586","author":"Linial N.","year":"2002","unstructured":"Linial , N. 2002 . Finite metric spaces---combinatorics, geometry and algorithms . In Proceedings of the International Congress of Mathematicians III. 573--586 . Linial, N. 2002. Finite metric spaces---combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III. 573--586."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","article-title":"The geometry of graphs and some of its algorithmic applications","volume":"15","author":"Linial N.","year":"1995","unstructured":"Linial , N. , London , E. , and Rabinovich , Y. 1995 . The geometry of graphs and some of its algorithmic applications . Combinatorica 15 , 215 -- 245 . Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215--245.","journal-title":"Combinatorica"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02761110","article-title":"On the distortion required for embedding finite metric spaces into normed spaces","volume":"93","author":"Matou\u0161ek J.","year":"1996","unstructured":"Matou\u0161ek , J. 1996 . On the distortion required for embedding finite metric spaces into normed spaces . Isr. J. Math. 93 , 333 -- 344 . Matou\u0161ek, J. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Isr. J. Math. 93, 333--344.","journal-title":"Isr. J. Math."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","volume":"212","author":"Matou\u0161ek J.","year":"2002","unstructured":"Matou\u0161ek , J. 2002 . Chapter 15: Embedding finite metric spaces into euclidean spaces . Lectures on Discrete Geometry. Graduate Texts in Mathematics , vol. 212 . Springer-Verlag. Matou\u0161ek, J. 2002. Chapter 15: Embedding finite metric spaces into euclidean spaces. Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer-Verlag."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 18th Annual Symposium on Computational Geometry. 94--96","author":"Newman I.","unstructured":"Newman , I. , and Rabinovich , Y . 2002. A lower bound on the distortion of embedding planar metrics into Euclidean space . In Proceedings of the 18th Annual Symposium on Computational Geometry. 94--96 . 10.1145\/513400.513412 Newman, I., and Rabinovich, Y. 2002. A lower bound on the distortion of embedding planar metrics into Euclidean space. In Proceedings of the 18th Annual Symposium on Computational Geometry. 94--96. 10.1145\/513400.513412"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Ostrovsky R.","unstructured":"Ostrovsky , R. , and Rabani , Y . 2000. Polynomial time approximation schemes for geometric k-clustering . In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 349--358. Ostrovsky, R., and Rabani, Y. 2000. Polynomial time approximation schemes for geometric k-clustering. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 349--358."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 15th Annual Symposium on Computational Geometry. 300--306","author":"Rao S.","year":"1999","unstructured":"Rao , S. 1999 . Small distortion and volume preserving embeddings for planar and Euclidean metrics . In Proceedings of the 15th Annual Symposium on Computational Geometry. 300--306 . 10.1145\/304893.304983 Rao, S. 1999. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry. 300--306. 10.1145\/304893.304983"},{"key":"e_1_2_1_28_1","first-page":"159","article-title":"More on embedding subspaces of Lp in &ell;nr. Composi","volume":"61","author":"Schechtman G.","year":"1987","unstructured":"Schechtman , G. 1987 . More on embedding subspaces of Lp in &ell;nr. Composi . Math. 61 , 2, 159 -- 169 . Schechtman, G. 1987. More on embedding subspaces of Lp in &ell;nr. Composi. Math. 61, 2, 159--169.","journal-title":"Math."},{"key":"e_1_2_1_29_1","first-page":"363","article-title":"Embedding subspaces of L1 into &ell;n1","volume":"108","author":"Talagrand M.","year":"1990","unstructured":"Talagrand , M. 1990 . Embedding subspaces of L1 into &ell;n1 . Proceedings of the American Mathetmatical Society , vol. 108 , 2, 363 -- 369 . Talagrand, M. 1990. Embedding subspaces of L1 into &ell;n1. Proceedings of the American Mathetmatical Society, vol. 108, 2, 363--369.","journal-title":"Proceedings of the American Mathetmatical Society"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089023.1089026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:22Z","timestamp":1750262902000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1089023.1089026"],"URL":"https:\/\/doi.org\/10.1145\/1089023.1089026","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}