{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:38:04Z","timestamp":1768030684123,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":78,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["200021 159697\/1, 200021 159697\/1"],"award-info":[{"award-number":["200021 159697\/1, 200021 159697\/1"]}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["788893"],"award-info":[{"award-number":["788893"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316318","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"1039-1050","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Oblivious dimension reduction for\n            <i>k<\/i>\n            -means: beyond subspaces and the Johnson-Lindenstrauss lemma"],"prefix":"10.1145","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Italy"}]},{"given":"Marc","family":"Bury","sequence":"additional","affiliation":[{"name":"Zalando, Switzerland"}]},{"given":"Vincent","family":"Cohen-Addad","sequence":"additional","affiliation":[{"name":"CNRS, France"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, Switzerland"}]},{"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Dimitris Achlioptas. 2003.  Dimitris Achlioptas. 2003."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"Ailon Nir","year":"2008","unstructured":"Nir Ailon and Edo Liberty . 2008 . Fast dimension reduction using Rademacher series on dual BCH codes . In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008 , San Francisco, California, USA , January 20-22, 2008. 1\u20139. Nir Ailon and Edo Liberty. 2008. Fast dimension reduction using Rademacher series on dual BCH codes. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008. 1\u20139."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483701"},{"key":"e_1_3_2_1_7_1","unstructured":"Noga Alon and Bo\u2019az Klartag. 2017.  Noga Alon and Bo\u2019az Klartag. 2017."},{"key":"e_1_3_2_1_8_1","volume-title":"Compression of Approximate Inner Products and Dimension Reduction. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Optimal","year":"2017","unstructured":"Optimal Compression of Approximate Inner Products and Dimension Reduction. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , Berkeley, CA, USA , October 15-17, 2017 . 639\u2013650. Optimal Compression of Approximate Inner Products and Dimension Reduction. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. 639\u2013650."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.56"},{"key":"e_1_3_2_1_10_1","unstructured":"Pranjal Awasthi and Or Sheffet. 2012.  Pranjal Awasthi and Or Sheffet. 2012."},{"key":"e_1_3_2_1_11_1","volume-title":"APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. 37\u201349","author":"Spectral-Norm Improved","unstructured":"Improved Spectral-Norm Bounds for Clustering . In Approximation , Randomization, and Combinatorial Optimization . Algorithms and Techniques - 15th International Workshop , APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. 37\u201349 . Improved Spectral-Norm Bounds for Clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. 37\u201349."},{"key":"e_1_3_2_1_12_1","unstructured":"Joshua D. Batson Daniel A. Spielman and Nikhil Srivastava. 2012.  Joshua D. Batson Daniel A. Spielman and Nikhil Srivastava. 2012."},{"key":"e_1_3_2_1_13_1","volume-title":"1704\u20131721","author":"Sparsifiers Twice-Ramanujan","year":"2012","unstructured":"Twice-Ramanujan Sparsifiers . SIAM J. Comput . 41, 6 ( 2012 ), 1704\u20131721 . Twice-Ramanujan Sparsifiers. SIAM J. Comput. 41, 6 (2012), 1704\u20131721."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746541"},{"key":"e_1_3_2_1_15_1","unstructured":"Christos Boutsidis and Malik Magdon-Ismail. 2013.  Christos Boutsidis and Malik Magdon-Ismail. 2013."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2255021"},{"key":"e_1_3_2_1_17_1","volume-title":"Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held","author":"Boutsidis Christos","year":"2009","unstructured":"Christos Boutsidis , Michael W. Mahoney , and Petros Drineas . 2009 . Unsupervised Feature Selection for the $k$-means Clustering Problem . In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada. 153\u2013161. STOC \u201919, June 23\u201326 , 2019, Phoenix, AZ, USA Becchetti, Bury, Cohen-Addad, Grandoni, Schwiegelshohn Christos Boutsidis, Michael W. Mahoney, and Petros Drineas. 2009. Unsupervised Feature Selection for the $k$-means Clustering Problem. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada. 153\u2013161. STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA Becchetti, Bury, Cohen-Addad, Grandoni, Schwiegelshohn"},{"key":"e_1_3_2_1_18_1","volume-title":"Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held","author":"Boutsidis Christos","year":"2010","unstructured":"Christos Boutsidis , Anastasios Zouzias , and Petros Drineas . 2010 . Random Projections for $k$-means Clustering . In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada. 298\u2013306. Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. 2010. Random Projections for $k$-means Clustering. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada. 298\u2013306."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2375327"},{"key":"e_1_3_2_1_20_1","unstructured":"Vladimir Braverman Dan Feldman and Harry Lang. 2016.  Vladimir Braverman Dan Feldman and Harry Lang. 2016."},{"key":"e_1_3_2_1_21_1","volume-title":"CoRR abs\/1612.00889","author":"Offline New Frameworks","year":"2016","unstructured":"New Frameworks for Offline and Streaming Coreset Constructions . CoRR abs\/1612.00889 ( 2016 ). New Frameworks for Offline and Streaming Coreset Constructions. CoRR abs\/1612.00889 (2016)."},{"key":"e_1_3_2_1_22_1","unstructured":"arXiv: 1612.00889 http:\/\/arxiv.org\/abs\/1612.00889  arXiv: 1612.00889 http:\/\/arxiv.org\/abs\/1612.00889"},{"key":"e_1_3_2_1_23_1","unstructured":"Vladimir Braverman Harry Lang Keith Levin and Morteza Monemizadeh. 2016.  Vladimir Braverman Harry Lang Keith Levin and Morteza Monemizadeh. 2016."},{"key":"e_1_3_2_1_24_1","volume-title":"Problems on Sliding Windows. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","author":"Clustering","year":"2016","unstructured":"Clustering Problems on Sliding Windows. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 , Arlington, VA, USA , January 10-12, 2016 . 1374\u20131390. Clustering Problems on Sliding Windows. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. 1374\u20131390."},{"key":"e_1_3_2_1_25_1","unstructured":"S. Charles Brubaker and Santosh Vempala. 2008.  S. Charles Brubaker and Santosh Vempala. 2008."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.48"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"e_1_3_2_1_28_1","volume-title":"Woodruff","author":"Clarkson Kenneth L.","year":"2016","unstructured":"Kenneth L. Clarkson , Petros Drineas , Malik Magdon-Ismail , Michael W. Mahoney , Xiangrui Meng , and David P . Woodruff . 2016 . Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, and David P. Woodruff. 2016."},{"key":"e_1_3_2_1_29_1","volume-title":"763\u2013810","author":"Cauchy Transform The Fast","year":"2016","unstructured":"The Fast Cauchy Transform and Faster Robust Linear Regression . SIAM J. Comput . 45, 3 ( 2016 ), 763\u2013810 . The Fast Cauchy Transform and Faster Robust Linear Regression. SIAM J. Comput. 45, 3 (2016), 763\u2013810."},{"key":"e_1_3_2_1_30_1","volume-title":"Woodruff","author":"Clarkson Kenneth L.","year":"2009","unstructured":"Kenneth L. Clarkson and David P . Woodruff . 2009 . Kenneth L. Clarkson and David P. Woodruff. 2009."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_3_2_1_32_1","volume-title":"Woodruff","author":"Clarkson Kenneth L.","year":"2013","unstructured":"Kenneth L. Clarkson and David P . Woodruff . 2013 . Kenneth L. Clarkson and David P. Woodruff. 2013."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884456"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746569"},{"key":"e_1_3_2_1_36_1","unstructured":"Michael B. Cohen T. S. Jayram and Jelani Nelson. 2018.  Michael B. Cohen T. S. Jayram and Jelani Nelson. 2018."},{"key":"e_1_3_2_1_37_1","volume-title":"Analyses of the Sparse Johnson-Lindenstrauss Transform. In 1st Symposium on Simplicity in Algorithms, SOSA 2018","author":"Simple","year":"2018","unstructured":"Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. In 1st Symposium on Simplicity in Algorithms, SOSA 2018 , January 7-10, 2018 , New Orleans, LA, USA. 15:1\u201315:9. Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA. 15:1\u201315:9."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039801"},{"key":"e_1_3_2_1_39_1","volume-title":"On the Local Structure of Stable Clustering Instances. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Cohen-Addad Vincent","year":"2017","unstructured":"Vincent Cohen-Addad and Chris Schwiegelshohn . 2017 . On the Local Structure of Stable Clustering Instances. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , Berkeley, CA, USA , October 15-17, 2017. 49\u201360. Vincent Cohen-Addad and Chris Schwiegelshohn. 2017. On the Local Structure of Stable Clustering Instances. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. 49\u201360."},{"key":"e_1_3_2_1_40_1","unstructured":"Anirban Dasgupta Ravi Kumar and Tam\u00e1s Sarl\u00f3s. 2010.  Anirban Dasgupta Ravi Kumar and Tam\u00e1s Sarl\u00f3s. 2010."},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"A","year":"2010","unstructured":"A sparse Johnson-Lindenstrauss transform. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010 , Cambridge, Massachusetts, USA , 5-8 June 2010 . 341\u2013350. A sparse Johnson-Lindenstrauss transform. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. 341\u2013350."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_3_2_1_43_1","unstructured":"Michael Elkin Arnold Filtser and Ofer Neiman. 2017.  Michael Elkin Arnold Filtser and Ofer Neiman. 2017."},{"key":"e_1_3_2_1_44_1","volume-title":"1\u201336","author":"Theor Terminal","year":"2017","unstructured":"Terminal embeddings. Theor . Comput. Sci. 697 ( 2017 ), 1\u201336 . Terminal embeddings. Theor. Comput. Sci. 697 (2017), 1\u201336."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247072"},{"key":"e_1_3_2_1_47_1","unstructured":"11\u201318.  11\u201318."},{"key":"e_1_3_2_1_48_1","unstructured":"Dan Feldman Melanie Schmidt and Christian Sohler. 2013.  Dan Feldman Melanie Schmidt and Christian Sohler. 2013."},{"key":"e_1_3_2_1_49_1","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013","author":"Turning","year":"2013","unstructured":"Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering . In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 , New Orleans, Louisiana, USA , January 6-8, 2013 . 1434\u2013 1453. Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013. 1434\u2013 1453."},{"key":"e_1_3_2_1_50_1","unstructured":"Gereon Frahling and Christian Sohler. 2005.  Gereon Frahling and Christian Sohler. 2005."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060622"},{"key":"e_1_3_2_1_52_1","volume-title":"Smaller Coresets for k-Median and k-Means Clustering. Discrete &amp","author":"Har-Peled Sariel","year":"2007","unstructured":"Sariel Har-Peled and Akash Kushal . 2007. Smaller Coresets for k-Median and k-Means Clustering. Discrete &amp ; Computational Geometry 37, 1 ( 2007 ), 3\u201319. Sariel Har-Peled and Akash Kushal. 2007. Smaller Coresets for k-Median and k-Means Clustering. Discrete &amp; Computational Geometry 37, 1 (2007), 3\u201319."},{"key":"e_1_3_2_1_53_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Har-Peled Sariel","year":"2004","unstructured":"Sariel Har-Peled and Soham Mazumdar . 2004 . On coresets for k-means and kmedian clustering . In Proceedings of the 36th Annual ACM Symposium on Theory of Computing , Chicago, IL, USA , June 13-16, 2004. 291\u2013300. Sariel Har-Peled and Soham Mazumdar. 2004. On coresets for k-means and kmedian clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. 291\u2013300."},{"key":"e_1_3_2_1_54_1","volume-title":"Woodruff","author":"Jayram T. S.","year":"2013","unstructured":"T. S. Jayram and David P . Woodruff . 2013 . T. S. Jayram and David P. Woodruff. 2013."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"e_1_3_2_1_56_1","volume-title":"Extensions of Lipschitz maps into a Hilbert space. 26 (01","author":"Johnson William","year":"1984","unstructured":"William Johnson and Joram Lindenstrauss . 1984. Extensions of Lipschitz maps into a Hilbert space. 26 (01 1984 ), 189\u2013206. William Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz maps into a Hilbert space. 26 (01 1984), 189\u2013206."},{"key":"e_1_3_2_1_57_1","volume-title":"APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 628\u2013639","author":"Kane Daniel M.","year":"2011","unstructured":"Daniel M. Kane , Raghu Meka , and Jelani Nelson . 2011 . Almost Optimal Explicit Johnson-Lindenstrauss Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop , APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 628\u2013639 . Daniel M. Kane, Raghu Meka, and Jelani Nelson. 2011. Almost Optimal Explicit Johnson-Lindenstrauss Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 628\u2013639."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559902"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445925"},{"key":"e_1_3_2_1_60_1","unstructured":"Amit Kumar and Ravindran Kannan. 2010.  Amit Kumar and Ravindran Kannan. 2010."},{"key":"e_1_3_2_1_61_1","volume-title":"51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26","author":"Spectral Clustering","year":"2010","unstructured":"Clustering with Spectral Norm and the k-Means Algorithm . In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26 , 2010 , Las Vegas, Nevada, USA. 299\u2013308. Clustering with Spectral Norm and the k-Means Algorithm. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA. 299\u2013308."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.50"},{"key":"e_1_3_2_1_63_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15","author":"Larsen Kasper Green","year":"2016","unstructured":"Kasper Green Larsen and Jelani Nelson . 2016 . The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15 , 2016, Rome, Italy. 82:1\u201382:11. Kasper Green Larsen and Jelani Nelson. 2016. The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. 82:1\u201382:11."},{"key":"e_1_3_2_1_64_1","unstructured":"Kasper Green Larsen and Jelani Nelson. 2017.  Kasper Green Larsen and Jelani Nelson. 2017."},{"key":"e_1_3_2_1_65_1","volume-title":"Johnson-Lindenstrauss Lemma. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Optimality","year":"2017","unstructured":"Optimality of the Johnson-Lindenstrauss Lemma. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , Berkeley, CA, USA , October 15-17, 2017 . 633\u2013638. Optimality of the Johnson-Lindenstrauss Lemma. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. 633\u2013638."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188828"},{"key":"e_1_3_2_1_67_1","volume-title":"APPROX\/RANDOM 2016","author":"Makarychev Konstantin","year":"2016","unstructured":"Konstantin Makarychev , Yury Makarychev , Maxim Sviridenko , and Justin Ward . 2016 . A Bi-Criteria Approximation Algorithm for k-Means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2016 , September 7-9, 2016, Paris, France. 14:1\u201314:20. Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward. 2016. A Bi-Criteria Approximation Algorithm for k-Means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2016, September 7-9, 2016, Paris, France. 14:1\u201314:20."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"crossref","unstructured":"Shyam Narayanan and Jelani Nelson. 2018.  Shyam Narayanan and Jelani Nelson. 2018.","DOI":"10.1007\/JHEP03(2018)171"},{"key":"e_1_3_2_1_70_1","volume-title":"CoRR abs\/1810.09250","author":"Optimal","year":"2018","unstructured":"Optimal terminal dimensionality reduction in Euclidean space. CoRR abs\/1810.09250 ( 2018 ). Optimal terminal dimensionality reduction in Euclidean space. CoRR abs\/1810.09250 (2018)."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488622"},{"key":"e_1_3_2_1_73_1","volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 883\u2013894","author":"Nelson Jelani","unstructured":"Jelani Nelson and Huy L. Nguy\u00ean . 2014. Lower Bounds for Oblivious Subspace Embeddings. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 883\u2013894 . Jelani Nelson and Huy L. Nguy\u00ean. 2014. Lower Bounds for Oblivious Subspace Embeddings. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 883\u2013894."},{"key":"e_1_3_2_1_74_1","unstructured":"Tam\u00e1s Sarl\u00f3s. 2006.  Tam\u00e1s Sarl\u00f3s. 2006."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00081"},{"key":"e_1_3_2_1_77_1","unstructured":"Santosh Vempala and Grant Wang. 2004.  Santosh Vempala and Grant Wang. 2004."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316318","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":78,"alternative-id":["10.1145\/3313276.3316318","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316318","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}