{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:11Z","timestamp":1778807891145,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":18,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Education of Singapore","award":["MOE2018-T2-1-013"],"award-info":[{"award-number":["MOE2018-T2-1-013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,12]]},"DOI":"10.1145\/3517804.3526224","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T13:29:54Z","timestamp":1655126994000},"page":"251-260","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for Sparse Oblivious Subspace Embeddings"],"prefix":"10.1145","author":[{"given":"Yi","family":"Li","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingmou","family":"Liu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/130919222"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2375327"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884456"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746569"},{"key":"e_1_3_2_2_6_1","unstructured":"Oracle Corporation. 2022. Oracle Database SQL Reference. https:\/\/docs.oracle.com\/cd\/B19306_01\/server.102\/b14200\/functions132.htm. Accessed: 2022-02--28.  Oracle Corporation. 2022. Oracle Database SQL Reference. https:\/\/docs.oracle.com\/cd\/B19306_01\/server.102\/b14200\/functions132.htm. Accessed: 2022-02--28."},{"key":"e_1_3_2_2_7_1","unstructured":"The Apache Software Foundation. 2022. Apache Spark Machine Learning Library (MLlib) Guide. https:\/\/spark.apache.org\/docs\/latest\/ml-classification-regression.html#linear-regression. Accessed: 2022-02--28.  The Apache Software Foundation. 2022. Apache Spark Machine Learning Library (MLlib) Guide. https:\/\/spark.apache.org\/docs\/latest\/ml-classification-regression.html#linear-regression. Accessed: 2022-02--28."},{"key":"e_1_3_2_2_8_1","unstructured":"The Apache Software Foundation and IBM. 2022. Apache SystemML. https:\/\/systemds.apache.org\/docs\/0.14.0\/algorithms-regression.html. Accessed: 2022-02--28.  The Apache Software Foundation and IBM. 2022. Apache SystemML. https:\/\/systemds.apache.org\/docs\/0.14.0\/algorithms-regression.html. Accessed: 2022-02--28."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367510"},{"key":"e_1_3_2_2_10_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"4806","author":"Jayaram Rajesh","year":"2021","unstructured":"Rajesh Jayaram , Alireza Samadian , David Woodruff , and Peng Ye . 2021 . In-Database Regression in Input Sparsity Time . In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research , Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 4797-- 4806 . https:\/\/proceedings.mlr.press\/v139\/jayaram21a.html Rajesh Jayaram, Alireza Samadian, David Woodruff, and Peng Ye. 2021. In-Database Regression in Input Sparsity Time. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 4797--4806. https:\/\/proceedings.mlr.press\/v139\/jayaram21a.html"},{"key":"e_1_3_2_2_11_1","volume-title":"Proceedings of the 2004 Annual National Conference on Digital Government Research","author":"Karr Alan F.","unstructured":"Alan F. Karr , Xiaodong Lin , Ashish P. Sanil , and Jerome P. Reiter . 2004. Regression on Distributed Databases via Secure Multi-Party Computation . In Proceedings of the 2004 Annual National Conference on Digital Government Research ( Seattle, WA, USA) (dg.o '04). Digital Government Society of North America, Article 108, 2 pages. Alan F. Karr, Xiaodong Lin, Ashish P. Sanil, and Jerome P. Reiter. 2004. Regression on Distributed Databases via Secure Multi-Party Computation. In Proceedings of the 2004 Annual National Conference on Digital Government Research (Seattle, WA, USA) (dg.o '04). Digital Government Society of North America, Article 108, 2 pages."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034795"},{"key":"e_1_3_2_2_13_1","volume-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science. 117--126","author":"Nelson J.","unstructured":"J. Nelson and H. L. Nguyen . 2013. OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings . In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. 117--126 . J. Nelson and H. L. Nguyen. 2013. OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. 117--126."},{"key":"e_1_3_2_2_14_1","volume-title":"Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing","author":"Nelson Jelani","year":"2013","unstructured":"Jelani Nelson and Huy L. Nguyen . 2013. Sparsity lower bounds for dimensionality reducing maps . In Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing ( Palo Alto, CA, USA) (STOC 2013 ), Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). Association for Computing Machinery, New York, NY, USA, 101--110. https:\/\/doi.org\/10.1145\/2488608.2488622 10.1145\/2488608.2488622 Jelani Nelson and Huy L. Nguyen. 2013. Sparsity lower bounds for dimensionality reducing maps. In Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing (Palo Alto, CA, USA) (STOC 2013), Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). Association for Computing Machinery, New York, NY, USA, 101--110. https:\/\/doi.org\/10.1145\/2488608.2488622"},{"key":"e_1_3_2_2_15_1","volume-title":"Nguyen","author":"Nelson Jelani","year":"2014","unstructured":"Jelani Nelson and Huy L . Nguyen . 2014 . Lower Bounds for Oblivious Subspace Embeddings. In Automata, Languages, and Programming, Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg, 883--894. Jelani Nelson and Huy L. Nguyen. 2014. Lower Bounds for Oblivious Subspace Embeddings. In Automata, Languages, and Programming, Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 883--894."},{"key":"e_1_3_2_2_16_1","volume-title":"47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21--24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society, 143--152","author":"Tam\u00e1","year":"2006","unstructured":"Tam\u00e1 s Sarl\u00f3 s. 2006 . Improved Approximation Algorithms for Large Matrices via Random Projections . In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21--24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society, 143--152 . https:\/\/doi.org\/10.1109\/FOCS.2006.37 10.1109\/FOCS.2006.37 Tam\u00e1 s Sarl\u00f3 s. 2006. Improved Approximation Algorithms for Large Matrices via Random Projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21--24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society, 143--152. https:\/\/doi.org\/10.1109\/FOCS.2006.37"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526224","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3526224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:05Z","timestamp":1750182545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":18,"alternative-id":["10.1145\/3517804.3526224","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3526224","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}