{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T18:34:51Z","timestamp":1791570891416,"version":"4.3.4"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","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":[],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1145\/2488608.2488622","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T12:35:41Z","timestamp":1369744541000},"page":"101-110","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Sparsity lower bounds for dimensionality reducing maps"],"prefix":"10.1145","author":[{"given":"Jelani","family":"Nelson","sequence":"first","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huy L.","family":"Nguy\u00c5n","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9110-x"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133053"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008917"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_26"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-6265-7"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873696"},{"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","doi-asserted-by":"publisher","DOI":"10.5555\/1793974.1793982"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2008.4797556"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9035-z"},{"key":"e_1_3_2_1_13_1","unstructured":"V. Braverman R. Ostrovsky and Y. Rabani. Rademacher chaos random Eulerian graphs and the sparse Johnson-Lindenstrauss transform. CoRR abs\/1011.2590 2010.  V. Braverman R. Ostrovsky and Y. Rabani. Rademacher chaos random Eulerian graphs and the sparse Johnson-Lindenstrauss transform. CoRR abs\/1011.2590 2010."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"E. J. Cand\u00e0s J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics 59(8) 2006.  E. J. Cand\u00e0s J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics 59(8) 2006.","DOI":"10.1002\/cpa.20124"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"e_1_3_2_1_19_1","volume-title":"Massachusetts Institute of Technology","author":"Chandar V. B.","year":"2010"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806737"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0114-x"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2173241"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning (ICML)","author":"Drineas P.","year":"2012"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/100806278"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90043-3"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553417"},{"key":"e_1_3_2_1_30_1","first-page":"200","article-title":"On the widths of the Euclidean ball","volume":"30","author":"Garnaev A. Y.","year":"1984","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0081737"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.82"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_36_1","unstructured":"D. M. Kane and J. Nelson. A derandomized sparse Johnson-Lindenstrauss transform. CoRR abs\/1006.3585 2010.  D. M. Kane and J. Nelson. A derandomized sparse Johnson-Lindenstrauss transform. CoRR abs\/1006.3585 2010."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095210"},{"issue":"2","key":"e_1_3_2_1_38_1","first-page":"334","article-title":"The widths of certain finite-dimensional sets and classes of smooth functions","volume":"41","author":"Kasin B. S.","year":"1977","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2004.10.009"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/100810447"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/mrm.21391"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:2"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_3_2_1_44_1","unstructured":"G. L. Miller and R. Peng. Iterative approaches to row sampling. CoRR abs\/1211.2713 2012.  G. L. Miller and R. Peng. Iterative approaches to row sampling. CoRR abs\/1211.2713 2012."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.07.002"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-008-9031-3"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2010.2042412"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"J. Nelson and H. L. Nguyen. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. CoRR abs\/1211.1002 2012.  J. Nelson and H. L. Nguyen. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. CoRR abs\/1211.1002 2012.","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/993490"},{"key":"e_1_3_2_1_51_1","volume-title":"Springer Verlag","author":"Talagrand M.","year":"2005"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"J. A. Tropp. Improved analysis of the subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. Special Issue on Sparse Representation of Data and Images 3(1--2):115--126 2011.  J. A. Tropp. Improved analysis of the subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. Special Issue on Sparse Representation of Data and Images 3(1--2):115--126 2011.","DOI":"10.1142\/S1793536911000787"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909108"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"S.\n       \n      Vempala\n    .\n      \n  \n   \n  The random projection method volume \n  65\n   of \n  DIMACS Series in Discrete Mathematics and Theoretical Computer Science\n  . \n  American Mathematical Society 2004\n  .  S. Vempala. The random projection method volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society 2004.","DOI":"10.1090\/dimacs\/065"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553516"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68880-8_32"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488622","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:20Z","timestamp":1750221560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":56,"alternative-id":["10.1145\/2488608.2488622","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488622","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}