{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:09:02Z","timestamp":1776283742994,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":84,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519946","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1038-1051","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Towards optimal lower bounds for k-median and k-means coresets"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Saulpic","sequence":"additional","affiliation":[{"name":"Sorbonne University, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_3_2_1_2_1","volume-title":"Geometric approximation via coresets. Combinatorial and computational geometry, 52","author":"Agarwal Pankaj K","year":"2005","unstructured":"Pankaj K Agarwal , Sariel Har-Peled , and Kasturi R Varadarajan . 2005. Geometric approximation via coresets. Combinatorial and computational geometry, 52 ( 2005 ), 1\u201330. Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. 2005. Geometric approximation via coresets. Combinatorial and computational geometry, 52 (2005), 1\u201330."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1171321"},{"key":"e_1_3_2_1_4_1","volume-title":"International Conference on Artificial Intelligence and Statistics, AISTATS 2018","volume":"792","author":"Bachem Olivier","year":"2018","unstructured":"Olivier Bachem , Mario Lucic , and Silvio Lattanzi . 2018 . One-shot Coresets: The Case of k-Clustering . In International Conference on Artificial Intelligence and Statistics, AISTATS 2018 , 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, Amos J. Storkey and Fernando P\u00e9rez-Cruz (Eds.) (Proceedings of Machine Learning Research , Vol. 84). PMLR, 784\u2013 792 . http:\/\/proceedings.mlr.press\/v84\/bachem18a.html Olivier Bachem, Mario Lucic, and Silvio Lattanzi. 2018. One-shot Coresets: The Case of k-Clustering. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, Amos J. Storkey and Fernando P\u00e9rez-Cruz (Eds.) (Proceedings of Machine Learning Research, Vol. 84). PMLR, 784\u2013792. http:\/\/proceedings.mlr.press\/v84\/bachem18a.html"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020","volume":"579","author":"Baker Daniel","year":"2020","unstructured":"Daniel Baker , Vladimir Braverman , Lingxiao Huang , Shaofeng H.-C. Jiang , Robert Krauthgamer , and Xuan Wu . 2020 . Coresets for Clustering in Graphs of Bounded Treewidth . In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 , 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research , Vol. 119). PMLR, 569\u2013 579 . http:\/\/proceedings.mlr.press\/v119\/baker20a.html Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. 2020. Coresets for Clustering in Graphs of Bounded Treewidth. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 569\u2013579. http:\/\/proceedings.mlr.press\/v119\/baker20a.html"},{"key":"e_1_3_2_1_6_1","volume-title":"On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. CoRR, abs\/2007.10137","author":"Bandyapadhyay Sayan","year":"2020","unstructured":"Sayan Bandyapadhyay , Fedor V. Fomin , and Kirill Simonov . 2020. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. CoRR, abs\/2007.10137 ( 2020 ), arxiv:2007.10137. arxiv:2007.10137 Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. 2020. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. CoRR, abs\/2007.10137 (2020), arxiv:2007.10137. arxiv:2007.10137"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316318"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2272457"},{"key":"e_1_3_2_1_9_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. http:\/\/papers.nips.cc\/paper\/3724-unsupervised-feature-selection-for-the-k-means-clustering-problem 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. http:\/\/papers.nips.cc\/paper\/3724-unsupervised-feature-selection-for-the-k-means-clustering-problem"},{"key":"e_1_3_2_1_10_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. http:\/\/papers.nips.cc\/paper\/3901-random-projections-for-k-means-clustering 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. http:\/\/papers.nips.cc\/paper\/3901-random-projections-for-k-means-clustering"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2375327"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.62"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Braverman Vladimir","year":"2017","unstructured":"Vladimir Braverman , Gereon Frahling , Harry Lang , Christian Sohler , and Lin F. Yang . 2017. Clustering High Dimensional Dynamic Data Streams . In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , Sydney, NSW, Australia , 6-11 August 2017 . 576\u2013585. http:\/\/proceedings.mlr.press\/v70\/braverman17a.html Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang. 2017. Clustering High Dimensional Dynamic Data Streams. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. 576\u2013585. http:\/\/proceedings.mlr.press\/v70\/braverman17a.html"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Braverman Vladimir","year":"2019","unstructured":"Vladimir Braverman , Shaofeng H.-C. Jiang , Robert Krauthgamer , and Xuan Wu . 2019 . Coresets for Ordered Weighted Clustering . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , 9-15 June 2019, Long Beach, California, USA. 744\u2013753. http:\/\/proceedings.mlr.press\/v97\/braverman19a.html Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. 2019. Coresets for Ordered Weighted Clustering. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. 744\u2013753. http:\/\/proceedings.mlr.press\/v97\/braverman19a.html"},{"key":"e_1_3_2_1_15_1","volume-title":"Coresets for Ordered Weighted Clustering. CoRR, abs\/1903.04351","author":"Braverman Vladimir","year":"2019","unstructured":"Vladimir Braverman , Shaofeng H.-C. Jiang , Robert Krauthgamer , and Xuan Wu. 2019. Coresets for Ordered Weighted Clustering. CoRR, abs\/1903.04351 ( 2019 ), arxiv:1903.04351. arxiv:1903.04351 Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. 2019. Coresets for Ordered Weighted Clustering. CoRR, abs\/1903.04351 (2019), arxiv:1903.04351. arxiv:1903.04351"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.159"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.159"},{"key":"e_1_3_2_1_18_1","volume-title":"Coresets for Clustering with Missing Values. CoRR, abs\/2106.16112","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman , Shaofeng H.-C. Jiang , Robert Krauthgamer , and Xuan Wu. 2021. Coresets for Clustering with Missing Values. CoRR, abs\/2106.16112 ( 2021 ), arXiv:2106.16112. arxiv:2106.16112 Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. 2021. Coresets for Clustering with Missing Values. CoRR, abs\/2106.16112 (2021), arXiv:2106.16112. arxiv:2106.16112"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch95"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.50"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9165-3"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"e_1_3_2_1_23_1","volume-title":"Terminal Embeddings in Sublinear Time. CoRR, abs\/2110.08691","author":"Cherapanamjeri Yeshwanth","year":"2021","unstructured":"Yeshwanth Cherapanamjeri and Jelani Nelson . 2021. Terminal Embeddings in Sublinear Time. CoRR, abs\/2110.08691 ( 2021 ), arXiv:2110.08691. arxiv:2110.08691 Yeshwanth Cherapanamjeri and Jelani Nelson. 2021. Terminal Embeddings in Sublinear Time. CoRR, abs\/2110.08691 (2021), arXiv:2110.08691. arxiv:2110.08691"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746569"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.29"},{"key":"e_1_3_2_1_26_1","volume-title":"Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. CoRR, abs\/2204.04828","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad , Hossein Esfandiari , Vahab S. Mirrokni , and Shyam Narayanan . 2022. Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. CoRR, abs\/2204.04828 ( 2022 ), https:\/\/doi.org\/10.48550\/arXiv.2204.04828 arXiv:2204.04828. 10.48550\/arXiv.2204.04828 Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. 2022. Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. CoRR, abs\/2204.04828 (2022), https:\/\/doi.org\/10.48550\/arXiv.2204.04828 arXiv:2204.04828."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477541"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.63"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M112717X"},{"key":"e_1_3_2_1_30_1","volume-title":"David Saulpic, and Chris Schwiegelshohn.","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad , Kasper Green Larsen , David Saulpic, and Chris Schwiegelshohn. 2022 . Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR , abs\/2202.12793 (2022), arxiv:2202.12793 Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. 2022. Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR, abs\/2202.12793 (2022), arxiv:2202.12793"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.41"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.33"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00040"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.156"},{"key":"e_1_3_2_1_35_1","volume-title":"Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad , David Saulpic , and Chris Schwiegelshohn . 2021. Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces . In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2021 , NeurIPS 2021, December 7-10, 2021, Virtual Conference, Alina Beygelzimer, Yann Dauphin, Percy Liang, and Jenn Wortman Vaughan (Eds .). Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. 2021. Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 7-10, 2021, Virtual Conference, Alina Beygelzimer, Yann Dauphin, Percy Liang, and Jenn Wortman Vaughan (Eds.)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451022"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.14"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.021"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11425-015-5049-6"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1335"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.53"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1209854"},{"key":"e_1_3_2_1_45_1","volume-title":"Woodruff","author":"Feng Zhili","year":"2019","unstructured":"Zhili Feng , Praneeth Kacham , and David P . Woodruff . 2019 . Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time. CoRR , abs\/1912.12003 (2019), arxiv:1912.12003. arxiv:1912.12003 Zhili Feng, Praneeth Kacham, and David P. Woodruff. 2019. Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time. CoRR, abs\/1912.12003 (2019), arxiv:1912.12003. arxiv:1912.12003"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_41"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060622"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106251"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1271-x"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00082"},{"key":"e_1_3_2_1_53_1","volume-title":"Coresets for Clustering with Fairness Constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Huang Lingxiao","year":"2019","unstructured":"Lingxiao Huang , Shaofeng H.-C. Jiang , and Nisheeth K. Vishnoi . 2019 . Coresets for Clustering with Fairness Constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019 , 8-14 December 2019, Vancouver, BC, Canada. 7587\u20137598. http:\/\/papers.nips.cc\/paper\/8976-coresets-for-clustering-with-fairness-constraints Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. 2019. Coresets for Clustering with Fairness Constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada. 7587\u20137598. http:\/\/papers.nips.cc\/paper\/8976-coresets-for-clustering-with-fairness-constraints"},{"key":"e_1_3_2_1_54_1","volume-title":"Coresets for Regressions with Panel Data. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Huang Lingxiao","year":"2020","unstructured":"Lingxiao Huang , K. Sudhir , and Nisheeth K. Vishnoi . 2020 . Coresets for Regressions with Panel Data. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020 , December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/03287fcce194dbd958c2ec5b33705912-Abstract.html Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. 2020. Coresets for Regressions with Panel Data. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/03287fcce194dbd958c2ec5b33705912-Abstract.html"},{"key":"e_1_3_2_1_55_1","volume-title":"Vishnoi","author":"Huang Lingxiao","year":"2021","unstructured":"Lingxiao Huang , K. Sudhir , and Nisheeth K . Vishnoi . 2021 . Coresets for Time Series Clustering . arxiv:2110.15263. Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. 2021. Coresets for Time Series Clustering. arxiv:2110.15263."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384296"},{"key":"e_1_3_2_1_57_1","volume-title":"Coresets for Scalable Bayesian Logistic Regression. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016","author":"Huggins Jonathan H.","year":"2016","unstructured":"Jonathan H. Huggins , Trevor Campbell , and Tamara Broderick . 2016 . Coresets for Scalable Bayesian Logistic Regression. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016 , December 5-10, 2016, Barcelona, Spain, Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (Eds.). 4080\u20134088. https:\/\/proceedings.neurips.cc\/paper\/ 2016\/hash\/2b0f658cbffd284984fb11d90254081f-Abstract.html Jonathan H. Huggins, Trevor Campbell, and Tamara Broderick. 2016. Coresets for Scalable Bayesian Logistic Regression. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (Eds.). 4080\u20134088. https:\/\/proceedings.neurips.cc\/paper\/2016\/hash\/2b0f658cbffd284984fb11d90254081f-Abstract.html"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.103"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594560"},{"key":"e_1_3_2_1_60_1","volume-title":"Coresets for Kernel Clustering. CoRR, abs\/2110.02898","author":"Jiang Shaofeng H.-C.","year":"2021","unstructured":"Shaofeng H.-C. Jiang , Robert Krauthgamer , Jianing Lou , and Yubo Zhang . 2021. Coresets for Kernel Clustering. CoRR, abs\/2110.02898 ( 2021 ), arXiv:2110.02898. arxiv:2110.02898 Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, and Yubo Zhang. 2021. Coresets for Kernel Clustering. CoRR, abs\/2110.02898 (2021), arXiv:2110.02898. arxiv:2110.02898"},{"key":"e_1_3_2_1_61_1","volume-title":"Coresets for Decision Trees of Signals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021","author":"Jubran Ibrahim","year":"2021","unstructured":"Ibrahim Jubran , Ernesto Evgeniy Sanches Shayda , Ilan Newman , and Dan Feldman . 2021 . Coresets for Decision Trees of Signals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021 , NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 30352\u201330364. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/fea9c11c4ad9a395a636ed944a28b51a-Abstract.html Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, and Dan Feldman. 2021. Coresets for Decision Trees of Signals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 30352\u201330364. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/fea9c11c4ad9a395a636ed944a28b51a-Abstract.html"},{"key":"e_1_3_2_1_62_1","volume-title":"Sets Clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020","volume":"5005","author":"Jubran Ibrahim","year":"2020","unstructured":"Ibrahim Jubran , Murad Tukan , Alaa Maalouf , and Dan Feldman . 2020 . Sets Clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 , 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research , Vol. 119). PMLR, 4994\u2013 5005 . http:\/\/proceedings.mlr.press\/v119\/jubran20a.html Ibrahim Jubran, Murad Tukan, Alaa Maalouf, and Dan Feldman. 2020. Sets Clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 4994\u20135005. http:\/\/proceedings.mlr.press\/v119\/jubran20a.html"},{"key":"e_1_3_2_1_63_1","volume-title":"Conference on Learning Theory, COLT 2019","volume":"1993","author":"Zohar","year":"2019","unstructured":"Zohar S. Karnin and Edo Liberty. 2019. Discrepancy, Coresets, and Sketches in Machine Learning . In Conference on Learning Theory, COLT 2019 , 25-28 June 2019 , Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research , Vol. 99). PMLR, 1975\u2013 1993 . http:\/\/proceedings.mlr.press\/v99\/karnin19a.html Zohar S. Karnin and Edo Liberty. 2019. Discrepancy, Coresets, and Sketches in Machine Learning. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 1975\u20131993. http:\/\/proceedings.mlr.press\/v99\/karnin19a.html"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702404055"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.50"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.64"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.11.009"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"e_1_3_2_1_70_1","article-title":"Training Gaussian Mixture Models at Scale via Coresets","volume":"18","author":"Lucic Mario","year":"2017","unstructured":"Mario Lucic , Matthew Faulkner , Andreas Krause , and Dan Feldman . 2017 . Training Gaussian Mixture Models at Scale via Coresets . J. Mach. Learn. Res. , 18 (2017), 160:1\u2013160:25. http:\/\/jmlr.org\/papers\/v18\/15-506.html Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. 2017. Training Gaussian Mixture Models at Scale via Coresets. J. Mach. Learn. Res., 18 (2017), 160:1\u2013160:25. http:\/\/jmlr.org\/papers\/v18\/15-506.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_71_1","volume-title":"Fast and Accurate Least-Mean-Squares Solvers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Maalouf Alaa","year":"2019","unstructured":"Alaa Maalouf , Ibrahim Jubran , and Dan Feldman . 2019 . Fast and Accurate Least-Mean-Squares Solvers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 8305\u20138316. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/475fbefa9ebfba9233364533aafd02a3-Abstract.html Alaa Maalouf, Ibrahim Jubran, and Dan Feldman. 2019. Fast and Accurate Least-Mean-Squares Solvers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 8305\u20138316. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/475fbefa9ebfba9233364533aafd02a3-Abstract.html"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188828"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"e_1_3_2_1_76_1","volume-title":"Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18)","author":"Molina Alejandro","year":"2018","unstructured":"Alejandro Molina , Alexander Munteanu , and Kristian Kersting . 2018 . Core Dependency Networks . In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18) , the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA , February 2-7, 2018, Sheila A. McIlraith and Kilian Q. Weinberger (Eds.). AAAI Press, 3820\u20133827. https:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI18\/paper\/view\/16847 Alejandro Molina, Alexander Munteanu, and Kristian Kersting. 2018. Core Dependency Networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, Sheila A. McIlraith and Kilian Q. Weinberger (Eds.). AAAI Press, 3820\u20133827. https:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI18\/paper\/view\/16847"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-017-0519-3"},{"key":"e_1_3_2_1_78_1","volume-title":"On Coresets for Logistic Regression. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Munteanu Alexander","year":"2018","unstructured":"Alexander Munteanu , Chris Schwiegelshohn , Christian Sohler , and David P. Woodruff . 2018 . On Coresets for Logistic Regression. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 , NeurIPS 2018 , December 3-8, 2018, Montr\u00e9al, Canada, Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett (Eds.). 6562\u20136571. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/63bfd6e8f26d1d3537f4c5038264ef36-Abstract.html Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. 2018. On Coresets for Logistic Regression. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada, Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett (Eds.). 6562\u20136571. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/63bfd6e8f26d1d3537f4c5038264ef36-Abstract.html"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316307"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00134-6"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39479-0_16"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00081"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1065725175"},{"key":"e_1_3_2_1_84_1","volume-title":"Coresets for Near-Convex Functions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Tukan Murad","year":"2020","unstructured":"Murad Tukan , Alaa Maalouf , and Dan Feldman . 2020 . Coresets for Near-Convex Functions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/0afe095e81a6ac76ff3f69975cb3e7ae-Abstract.html Murad Tukan, Alaa Maalouf, and Dan Feldman. 2020. Coresets for Near-Convex Functions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/0afe095e81a6ac76ff3f69975cb3e7ae-Abstract.html"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519946","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519946","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519946"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":84,"alternative-id":["10.1145\/3519935.3519946","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519946","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}