{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:24:18Z","timestamp":1765355058721,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Division of Mathematical Sciences","award":["2054408"],"award-info":[{"award-number":["2054408"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649762","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1106-1117","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal Embedding Dimension for Sparse Subspace Embeddings"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8005-5631","authenticated-orcid":false,"given":"Shabarish","family":"Chenakkod","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7274-539X","authenticated-orcid":false,"given":"Micha\u0142","family":"Derezi\u0144ski","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3729-1433","authenticated-orcid":false,"given":"Xiaoyu","family":"Dong","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5730-0034","authenticated-orcid":false,"given":"Mark","family":"Rudelson","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"SIAM Journal on computing, 39, 1","volume-title":"The fast Johnson\u2013Lindenstrauss transform and approximate nearest neighbors","author":"Ailon Nir","year":"2009","unstructured":"Nir Ailon and Bernard Chazelle. 2009. The fast Johnson\u2013Lindenstrauss transform and approximate nearest neighbors. SIAM Journal on computing, 39, 1 (2009), 302\u2013322."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Afonso S Bandeira March T Boedihardjo and Ramon van Handel. 2023. Matrix concentration inequalities and free probability. Inventiones mathematicae 1\u201369.","DOI":"10.1007\/s00222-023-01204-6"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746541"},{"key":"e_1_3_2_1_4_1","unstructured":"Tatiana Brailovskaya and Ramon van Handel. 2022. Universality and sharp matrix concentration inequalities. arXiv preprint arXiv:2201.05142."},{"key":"e_1_3_2_1_5_1","unstructured":"Coralia Cartis Jan Fiala and Zhen Shao. 2021. Hashing embeddings of optimal dimension with applications to linear least squares. arXiv preprint arXiv:2105.11815."},{"key":"e_1_3_2_1_6_1","volume-title":"Conference on Learning Theory. 1144\u20131179","author":"Chen Xue","year":"2021","unstructured":"Xue Chen and Michal Derezi\u0144ski. 2021. Query complexity of least absolute deviation regression via robust uniform convergence. In Conference on Learning Theory. 1144\u20131179."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.118"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch154"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/140963698"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884456"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.115"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746567"},{"key":"e_1_3_2_1_16_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 3137\u20133172","author":"Derezi\u0144ski Micha\u0142","year":"2023","unstructured":"Micha\u0142 Derezi\u0144ski. 2023. Algorithmic gaussianization through sketching: Converting data into sub-gaussian random designs. In The Thirty Sixth Annual Conference on Learning Theory. 3137\u20133172."},{"key":"e_1_3_2_1_17_1","first-page":"2835","article-title":"Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update","volume":"34","author":"Derezi\u0144ski Micha\u0142","year":"2021","unstructured":"Micha\u0142 Derezi\u0144ski, Jonathan Lacotte, Mert Pilanci, and Michael W Mahoney. 2021. Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update. Advances in Neural Information Processing Systems, 34 (2021), 2835\u20132847.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_18_1","volume-title":"Conference on Learning Theory. 1467\u20131510","author":"Derezi\u0144ski Micha\u0142","year":"2021","unstructured":"Micha\u0142 Derezi\u0144ski, Zhenyu Liao, Edgar Dobriban, and Michael Mahoney. 2021. Sparse sketches with small inversion bias. In Conference on Learning Theory. 1467\u20131510."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/noti2202"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1545537"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503352"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2842602"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. 1127\u20131136","author":"Drineas Petros","year":"2006","unstructured":"Petros Drineas, Michael W Mahoney, and S Muthukrishnan. 2006. Sampling algorithms for \u2113 _2 regression and applications. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. 1127\u20131136."},{"key":"e_1_3_2_1_24_1","series-title":"SIAM review, 53, 2","volume-title":"Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions","author":"Halko Nathan","year":"2011","unstructured":"Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. 2011. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53, 2 (2011), 217\u2013288."},{"key":"e_1_3_2_1_25_1","volume-title":"Swati Padmanabhan, and Zhao Song.","author":"Jiang Haotian","year":"2020","unstructured":"Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. 2020. A faster interior point method for semidefinite programming. In 2020 IEEE 61st annual symposium on foundations of computer science (FOCS). 910\u2013918."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_27_1","volume-title":"International Conference on Machine Learning. 6001\u20136009","author":"Li Yi","year":"2020","unstructured":"Yi Li and David Woodruff. 2020. Input-sparsity low rank approximation in Schatten norm. In International Conference on Machine Learning. 6001\u20136009."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_3_2_1_30_1","unstructured":"R. Murray J. Demmel M. W. Mahoney N. B. Erichson M. Melnichenko O. A. Malik L. Grigori M. Derezi\u0144ski M. E. Lopes T. Liang and H. Luo. 2023. Randomized Numerical Linear Algebra \u2013 A Perspective on the Field with an Eye to Software."},{"key":"e_1_3_2_1_31_1","volume-title":"OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science. 117\u2013126.","author":"Nelson Jelani","year":"2013","unstructured":"Jelani Nelson and Huy L Nguy\u00ean. 2013. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science. 117\u2013126."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Jelani Nelson and Huy L Nguy\u00ean. 2014. Lower bounds for oblivious subspace embeddings. In International Colloquium on Automata Languages and Programming. 883\u2013894.","DOI":"10.1007\/978-3-662-43948-7_73"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0804869105"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the International Congress of Mathematicians 2010 (ICM 2010)","volume":"1602","author":"Rudelson Mark","year":"2010","unstructured":"Mark Rudelson and Roman Vershynin. 2010. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures. 1576\u20131602."},{"volume-title":"Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS\u201906). 143\u2013152","author":"Sarlos Tamas","key":"e_1_3_2_1_35_1","unstructured":"Tamas Sarlos. 2006. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS\u201906). 143\u2013152."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.172"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793536911000787"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3477537","article-title":"Tight Bounds for \u21131 Oblivious Subspace Embeddings","volume":"18","author":"Wang Ruosong","year":"2022","unstructured":"Ruosong Wang and David P Woodruff. 2022. Tight Bounds for \u21131 Oblivious Subspace Embeddings. ACM Transactions on Algorithms (TALG), 18, 1 (2022), 1\u201332.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_39_1","volume-title":"Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science, 10, 1\u20132","author":"Woodruff David P","year":"2014","unstructured":"David P Woodruff. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science, 10, 1\u20132 (2014), 1\u2013157."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3242068"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649762","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":40,"alternative-id":["10.1145\/3618260.3649762","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649762","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}