{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:19:30Z","timestamp":1770895170712,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384311","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"140-152","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A polynomial lower bound on adaptive complexity of submodular maximization"],"prefix":"10.1145","author":[{"given":"Wenzheng","family":"Li","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Liu","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_1_2_1","volume-title":"Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/","author":"Balkanski Eric","year":"1807","unstructured":"Eric Balkanski , Adam Breuer , and Yaron Singer . 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/ 1807 .11462 ( 2018 ). arXiv: 1807.11462 http:\/\/arxiv.org\/abs\/ 1807.11462 Eric Balkanski, Adam Breuer, and Yaron Singer. 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/ 1807.11462 ( 2018 ). arXiv: 1807.11462 http:\/\/arxiv.org\/abs\/ 1807.11462"},{"key":"e_1_3_2_1_3_1","volume-title":"An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/","author":"Balkanski Eric","year":"1804","unstructured":"Eric Balkanski , Aviad Rubinstein , and Yaron Singer . 2018. An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/ 1804 .06355 ( 2018 ). arXiv: 1804.06355 http:\/\/arxiv. org\/abs\/ 1804.06355 Eric Balkanski, Aviad Rubinstein, and Yaron Singer. 2018. An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/ 1804.06355 ( 2018 ). arXiv: 1804.06355 http:\/\/arxiv. org\/abs\/ 1804.06355"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316304"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188752"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Balkanski Eric","year":"2018","unstructured":"Eric Balkanski and Yaron Singer . 2018 . Approximation Guarantees for Adaptive Sampling . In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan , Stockholm, Sweden , July 10-15, 2018. 393-402. http:\/\/proceedings.mlr.press\/v80\/balkanski18a.html Eric Balkanski and Yaron Singer. 2018. Approximation Guarantees for Adaptive Sampling. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018. 393-402. http:\/\/proceedings.mlr.press\/v80\/balkanski18a.html"},{"key":"e_1_3_2_1_7_1","volume-title":"The FAST Algorithm for Submodular Maximization. CoRR abs\/","author":"Breuer Adam","year":"1907","unstructured":"Adam Breuer , Eric Balkanski , and Yaron Singer . 2019. The FAST Algorithm for Submodular Maximization. CoRR abs\/ 1907 .06173 ( 2019 ). arXiv: 1907.06173 http:\/\/arxiv.org\/abs\/ 1907.06173 Adam Breuer, Eric Balkanski, and Yaron Singer. 2019. The FAST Algorithm for Submodular Maximization. CoRR abs\/ 1907.06173 ( 2019 ). arXiv: 1907.06173 http:\/\/arxiv.org\/abs\/ 1907.06173"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316406"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.20"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316327"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015","author":"da Ponte Barbosa Rafael","year":"2015","unstructured":"Rafael da Ponte Barbosa , Alina Ene , Huy L. Nguyen , and Justin Ward . 2015 . The Power of Randomization: Distributed Submodular Maximization on Massive Datasets . In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015 , Lille, France , 6-11 July 2015. 1236-1244. http:\/\/proceedings.mlr.press\/ v37\/barbosa15.html Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. 2015. The Power of Randomization: Distributed Submodular Maximization on Massive Datasets. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015. 1236-1244. http:\/\/proceedings.mlr.press\/ v37\/barbosa15.html"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.74"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.18"},{"key":"e_1_3_2_1_15_1","volume-title":"A Parallel Double Greedy Algorithm for Submodular Maximization. CoRR abs\/","author":"Ene Alina","year":"1812","unstructured":"Alina Ene , Huy L. Nguyen , and Adrian Vladu . 2018. A Parallel Double Greedy Algorithm for Submodular Maximization. CoRR abs\/ 1812 .01591 ( 2018 ). arXiv: 1812.01591 http:\/\/arxiv.org\/abs\/ 1812.01591 Alina Ene, Huy L. Nguyen, and Adrian Vladu. 2018. A Parallel Double Greedy Algorithm for Submodular Maximization. CoRR abs\/ 1812.01591 ( 2018 ). arXiv: 1812.01591 http:\/\/arxiv.org\/abs\/ 1812.01591"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316389"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Fahrbach Matthew","year":"2019","unstructured":"Matthew Fahrbach , Vahab S. Mirrokni , and Morteza Zadimoghaddam . 2019 . Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , 9-15 June 2019, Long Beach, California, USA. 1833-1842. http:\/\/proceedings.mlr.press\/v97\/fahrbach19a.html Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2019. Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. 1833-1842. http:\/\/proceedings.mlr.press\/v97\/fahrbach19a.html"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.17"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Kazemi Ehsan","year":"2019","unstructured":"Ehsan Kazemi , Marko Mitrovic , Morteza Zadimoghaddam , Silvio Lattanzi , and Amin Karbasi . 2019 . Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , 9-15 June 2019, Long Beach, California, USA. 3311-3320. http:\/\/proceedings.mlr.press\/v97\/kazemi19a. html Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. 2019. Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. 3311-3320. http:\/\/proceedings.mlr.press\/v97\/kazemi19a. html"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Andreas Krause and Daniel Golovin. 2014. Submodular Function Maximization. Tractability: Practical Approaches to Hard Problems ( 2014 ) 71-104.  Andreas Krause and Daniel Golovin. 2014. Submodular Function Maximization. Tractability: Practical Approaches to Hard Problems ( 2014 ) 71-104.","DOI":"10.1017\/CBO9781139177801.004"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2809814"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.18"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2017.22"},{"key":"e_1_3_2_1_26_1","volume-title":"Randomized Composable Core-sets for Distributed Submodular Maximization. In ACM Symposium on Theory of Computing (STOC). 153-162","author":"Vahab","unstructured":"Vahab S. Mirrokni and Morteza Zadimoghaddam. 2015 . Randomized Composable Core-sets for Distributed Submodular Maximization. In ACM Symposium on Theory of Computing (STOC). 153-162 . Vahab S. Mirrokni and Morteza Zadimoghaddam. 2015. Randomized Composable Core-sets for Distributed Submodular Maximization. In ACM Symposium on Theory of Computing (STOC). 153-162."},{"key":"e_1_3_2_1_27_1","volume-title":"Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems","author":"Mirzasoleiman Baharan","year":"2013","unstructured":"Baharan Mirzasoleiman , Amin Karbasi , Rik Sarkar , and Andreas Krause . 2013. Distributed Submodular Maximization: Identifying Representative Elements in Massive Data . In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013 . Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States . 2049-2057. http:\/\/papers.nips.cc\/paper\/5039-distributed-submodular-maximizationidentifying-representative-elements-in-massive-data Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. 2013. Distributed Submodular Maximization: Identifying Representative Elements in Massive Data. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. 2049-2057. http:\/\/papers.nips.cc\/paper\/5039-distributed-submodular-maximizationidentifying-representative-elements-in-massive-data"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.24"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384311","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:13Z","timestamp":1750200073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":30,"alternative-id":["10.1145\/3357713.3384311","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384311","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}