{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:52:07Z","timestamp":1768031527539,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,6]]},"abstract":"\n The Johnson-Lindenstrauss transform is a dimensionality reduction technique with a wide range of applications to theoretical computer science. It is specified by a distribution over projection matrices from R\n n<\/jats:sup>\n \u2192 R\n k<\/jats:sup>\n where\n k n<\/jats:italic>\n and states that\n k<\/jats:italic>\n =\n O<\/jats:italic>\n (\n \u03b5<\/jats:italic>\n \u22122<\/jats:sup>\n log 1\/\n \u03b4<\/jats:italic>\n ) dimensions suffice to approximate the norm of any fixed vector in R\n n<\/jats:sup>\n to within a factor of 1 \u00b1\n \u03b5<\/jats:italic>\n with probability at least 1 \u2212\n \u03b4<\/jats:italic>\n . In this article, we show that this bound on\n k<\/jats:italic>\n is optimal up to a constant factor, improving upon a previous\n \u03a9<\/jats:italic>\n ((\n \u03b5<\/jats:italic>\n \u22122<\/jats:sup>\n log<\/jats:italic>\n 1\/\n \u03b4<\/jats:italic>\n )\/log(1\/\n \u03b5<\/jats:italic>\n )) dimension bound of Alon. Our techniques are based on lower bounding the information cost of a novel one-way communication game and yield the first space lower bounds in a data stream model that depend on the error probability\n \u03b4<\/jats:italic>\n .\n <\/jats:p>\n \n For many streaming problems, the most na\u00efve way of achieving error probability\n \u03b4<\/jats:italic>\n is to first achieve constant probability, then take the median of\n O<\/jats:italic>\n (log 1\/\n \u03b4<\/jats:italic>\n ) independent repetitions. Our techniques show that for a wide range of problems, this is in fact optimal! As an example, we show that estimating the \u2113\n p<\/jats:sub>\n -distance for any\n p<\/jats:italic>\n \u2009\u2208\u2009[0,2] requires\n \u03a9<\/jats:italic>\n (\n \u03b5<\/jats:italic>\n \u22122<\/jats:sup>\n log\n n<\/jats:italic>\n log 1\/\n \u03b4<\/jats:italic>\n ) space, even for vectors in {0,1}\n n<\/jats:sup>\n . This is optimal in all parameters and closes a long line of work on this problem. We also show the number of distinct elements requires\n \u03a9<\/jats:italic>\n (\n \u03b5<\/jats:italic>\n \u22122<\/jats:sup>\n log 1\/\n \u03b4<\/jats:italic>\n + log\n n<\/jats:italic>\n ) space, which is optimal if\n \u03b5<\/jats:italic>\n \u22122<\/jats:sup>\n =\n \u03a9<\/jats:italic>\n (log\n n<\/jats:italic>\n ). We also improve previous lower bounds for entropy in the strict turnstile and general turnstile models by a multiplicative factor of\n \u03a9<\/jats:italic>\n (log 1\/\n \u03b4<\/jats:italic>\n ). Finally, we give an application to one-way communication complexity under product distributions, showing that, unlike the case of constant\n \u03b4<\/jats:italic>\n , the VC-dimension does not characterize the complexity when\n \u03b4<\/jats:italic>\n \u2009=\u2009\n o<\/jats:italic>\n (1).\n <\/jats:p>","DOI":"10.1145\/2483699.2483706","type":"journal-article","created":{"date-parts":[[2013,6,25]],"date-time":"2013-06-25T18:50:29Z","timestamp":1372186229000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error"],"prefix":"10.1145","volume":"9","author":[{"given":"T. S.","family":"Jayram","sequence":"first","affiliation":[{"name":"IBM Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"IBM Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1646353.1646379"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9110-x"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Nir Ailon and Edo Liberty. 2010. Almost optimal unrestricted fast Johnson-Lindenstrauss transform. CoRR abs\/1005.5513. Nir Ailon and Edo Liberty. 2010. Almost optimal unrestricted fast Johnson-Lindenstrauss transform. CoRR abs\/1005.5513.","DOI":"10.1137\/1.9781611973082.17"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_8_1","unstructured":"Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2010. Streaming algorithms from precision sampling. CoRR abs\/1011.1263. Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2010. Streaming algorithms from precision sampling. CoRR abs\/1011.1263."},{"key":"e_1_2_1_9_1","volume-title":"Arriaga and Santosh Vempala","author":"Rosa","year":"1999","unstructured":"Rosa I. Arriaga and Santosh Vempala . 1999 . An algorithmic theory of learning: Robust concepts and random projection. In Proceedings of FOCS. 616--623. Rosa I. Arriaga and Santosh Vempala. 1999. An algorithmic theory of learning: Robust concepts and random projection. In Proceedings of FOCS. 616--623."},{"key":"e_1_2_1_10_1","volume-title":"Woodruff","author":"Ba Khanh Do","year":"2010","unstructured":"Khanh Do Ba , Piotr Indyk , Eric C. Price , and David P . Woodruff . 2010 . Lower bounds for sparse recovery. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1190--1197. Khanh Do Ba, Piotr Indyk, Eric C. Price, and David P. Woodruff. 2010. Lower bounds for sparse recovery. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1190--1197."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC). 93--102","author":"Bar-Yossef Ziv","unstructured":"Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , and D. Sivakumar . 2002. Information theory methods in communication complexity . In Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC). 93--102 . Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. 2002. Information theory methods in communication complexity. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC). 93--102."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_24"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_2_1_14_1","volume-title":"Recursive sketching for frequency moments. CoRR abs\/1011.2571","author":"Braverman Vladimir","year":"2010","unstructured":"Vladimir Braverman and Rafail Ostrovsky . 2010. Recursive sketching for frequency moments. CoRR abs\/1011.2571 ( 2010 ). Vladimir Braverman and Rafail Ostrovsky. 2010. Recursive sketching for frequency moments. CoRR abs\/1011.2571 (2010)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875561"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377676.1377685"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of ESA. 148--160","author":"Cormode Graham","unstructured":"Graham Cormode and S. Muthukrishnan . 2003. Estimating dominance norms of multiple data streams . In Proceedings of ESA. 148--160 . Graham Cormode and S. Muthukrishnan. 2003. Estimating dominance norms of multiple data streams. In Proceedings of ESA. 148--160."},{"key":"e_1_2_1_22_1","volume-title":"Elements of Information Theory","author":"Cover Thomas","unstructured":"Thomas Cover and Joy Thomas . 1991. Elements of Information Theory . Wiley Interscience . Thomas Cover and Joy Thomas. 1991. Elements of Information Theory. Wiley Interscience."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806737"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"e_1_2_1_26_1","volume-title":"Polynomial estimators for high frequency moments. CoRR abs\/1104.4552","author":"Ganguly Sumit","year":"2011","unstructured":"Sumit Ganguly . 2011. Polynomial estimators for high frequency moments. CoRR abs\/1104.4552 ( 2011 ). Sumit Ganguly. 2011. Polynomial estimators for high frequency moments. CoRR abs\/1104.4552 (2011)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806755"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.32"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 283--288","author":"Indyk Piotr","unstructured":"Piotr Indyk and David P. Woodruff . 2003. Tight lower bounds for the distinct elements problem . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 283--288 . Piotr Indyk and David P. Woodruff. 2003. Tight lower bounds for the distinct elements problem. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 283--288."},{"key":"e_1_2_1_32_1","volume-title":"Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR abs\/0807.1267","author":"Jain Rahul","year":"2008","unstructured":"Rahul Jain , Pranab Sen , and Jaikumar Radhakrishnan . 2008. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR abs\/0807.1267 ( 2008 ). Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. 2008. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR abs\/0807.1267 (2008)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_34_1","volume-title":"Woodruff","author":"Kane Daniel M.","year":"2010","unstructured":"Daniel M. Kane , Jelani Nelson , and David P . Woodruff . 2010 a. On the exact space complexity of sketching and streaming small norms. In Proceedings of SODA. Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010a. On the exact space complexity of sketching and streaming small norms. In Proceedings of SODA."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"e_1_2_1_37_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_38_1","unstructured":"J. Langford L. Li and A. Strehl. 2007. Vowpal wabbit online learning. Tech. rep. http:\/\/hunch.net\/~p=309. J. Langford L. Li and A. Strehl. 2007. Vowpal wabbit online learning. Tech. rep. http:\/\/hunch.net\/~p=309."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_40"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643672"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736417"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of AISTATS 12","author":"Shi Q.","unstructured":"Q. Shi , J. Petterson , G. Dror , J. Langford , A. J. Smola , A. Strehl , and V. Vishwanathan . 2009. Hash kernels . In Proceedings of AISTATS 12 . Q. Shi, J. Petterson, G. Dror, J. Langford, A. J. Smola, A. Strehl, and V. Vishwanathan. 2009. Hash kernels. In Proceedings of AISTATS 12."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807337"},{"key":"e_1_2_1_48_1","volume-title":"Taqqu","author":"Stoev Stilian","year":"2010","unstructured":"Stilian Stoev and Murad S . Taqqu . 2010 . Max-stable sketches: Estimation of Lp-norms, dominance norms and point queries for non-negative signals. CoRR abs\/1005.4344 (2010). Stilian Stoev and Murad S. Taqqu. 2010. Max-stable sketches: Estimation of Lp-norms, dominance norms and point queries for non-negative signals. CoRR abs\/1005.4344 (2010)."},{"key":"e_1_2_1_49_1","volume-title":"Taqqu","author":"Stoev Stilian","year":"2007","unstructured":"Stilian Stoev , Marios Hadjieleftheriou , George Kollios , and Murad S . Taqqu . 2007 . Norm, point, and distance estimation over multiple signals using max-stable distributions. In Proceedings of ICDE. 1006--1015. Stilian Stoev, Marios Hadjieleftheriou, George Kollios, and Murad S. Taqqu. 2007. Norm, point, and distance estimation over multiple signals using max-stable distributions. In Proceedings of ICDE. 1006--1015."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.10.031"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 615--624","author":"Thorup Mikkel","year":"2004","unstructured":"Mikkel Thorup and Yin Zhang . 2004 . Tabulation based 4-universal hashing with applications to second moment estimation . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 615--624 . Mikkel Thorup and Yin Zhang. 2004. Tabulation based 4-universal hashing with applications to second moment estimation. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 615--624."},{"key":"e_1_2_1_52_1","unstructured":"S. Tirthapura and D. Woodruff. 2011. Approximating the Klee\u2019s measure problem on a stream of rectangles. Manuscript. S. Tirthapura and D. Woodruff. 2011. Approximating the Klee\u2019s measure problem on a stream of rectangles. Manuscript."},{"key":"e_1_2_1_53_1","volume-title":"Smola","author":"Weinberger Kilian Q.","year":"2009","unstructured":"Kilian Q. Weinberger , Anirban Dasgupta , Josh Attenberg , John Langford , and Alex J . Smola . 2009 . Feature hashing for large scale multitask learning. CoRR abs\/0902.2206 (2009). Kilian Q. Weinberger, Anirban Dasgupta, Josh Attenberg, John Langford, and Alex J. Smola. 2009. Feature hashing for large scale multitask learning. CoRR abs\/0902.2206 (2009)."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 167--175","author":"Woodruff David P.","year":"2004","unstructured":"David P. Woodruff . 2004 . Optimal space lower bounds for all frequency moments . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 167--175 . David P. Woodruff. 2004. Optimal space lower bounds for all frequency moments. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 167--175."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993733"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2483699.2483706","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2483699.2483706","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:36Z","timestamp":1750277676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2483699.2483706"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2483699.2483706"],"URL":"https:\/\/doi.org\/10.1145\/2483699.2483706","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}