{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:08Z","timestamp":1750220768805,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"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.3384287","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"130-139","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A lower bound for parallel submodular minimization"],"prefix":"10.1145","author":[{"given":"Eric","family":"Balkanski","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaron","family":"Singer","sequence":"additional","affiliation":[{"name":"Harvard 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\/3313276.3316361"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Brian Axelrod Yang P Liu and Aaron Sidford. 2019. Near-optimal Approximate Discrete and Continuous Submodular Function Minimization. arXiv preprint arXiv:1909.00171.  Brian Axelrod Yang P Liu and Aaron Sidford. 2019. Near-optimal Approximate Discrete and Continuous Submodular Function Minimization. arXiv preprint arXiv:1909.00171.","DOI":"10.1137\/1.9781611975994.51"},{"key":"e_1_3_2_1_3_1","unstructured":"Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems. 2353\u20132364.  Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems. 2353\u20132364."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310454"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316304"},{"key":"e_1_3_2_1_6_1","unstructured":"Eric Balkanski and Yaron Singer. 2017. Minimizing a submodular function from samples. In Advances in Neural Information Processing Systems. 814\u2013822.  Eric Balkanski and Yaron Singer. 2017. Minimizing a submodular function from samples. In Advances in Neural Information Processing Systems. 814\u2013822."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188752"},{"key":"e_1_3_2_1_8_1","unstructured":"Eric Balkanski and Yaron Singer. 2018. Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. arXiv preprint arXiv:1808.03880.  Eric Balkanski and Yaron Singer. 2018. Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. arXiv preprint arXiv:1808.03880."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"e_1_3_2_1_10_1","volume-title":"Yuanzhi Li, and Aaron Sidford.","author":"Bubeck S\u00e9bastien","year":"2019","unstructured":"S\u00e9bastien Bubeck , Qijia Jiang , Yin Tat Lee , Yuanzhi Li, and Aaron Sidford. 2019 . Complexity of Highly Parallel Non-Smooth Convex Optimization . arXiv preprint arXiv:1906.10655. S\u00e9bastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. 2019. Complexity of Highly Parallel Non-Smooth Convex Optimization. arXiv preprint arXiv:1906.10655."},{"key":"e_1_3_2_1_11_1","unstructured":"Deeparnab Chakrabarty Prateek Jain and Pravesh Kothari. 2014. Provable submodular minimization using Wolfe\u2019s algorithm. In Advances in Neural Information Processing Systems. 802\u2013809.  Deeparnab Chakrabarty Prateek Jain and Pravesh Kothari. 2014. Provable submodular minimization using Wolfe\u2019s algorithm. In Advances in Neural Information Processing Systems. 802\u2013809."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055419"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316406"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310455"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316327"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579361"},{"key":"e_1_3_2_1_17_1","unstructured":"Jelena Diakonikolas and Crist\u00f3bal Guzm\u00e1n. 2018. Lower bounds for parallel and randomized convex optimization. arXiv preprint arXiv:1811.01903.  Jelena Diakonikolas and Crist\u00f3bal Guzm\u00e1n. 2018. Lower bounds for parallel and randomized convex optimization. arXiv preprint arXiv:1811.01903."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110831659"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310453"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316389"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Matthew Fahrbach Vahab Mirrokni and Morteza Zadimoghaddam. 2019. Submodular maximization with optimal approximation adaptivity and query complexity. SODA.  Matthew Fahrbach Vahab Mirrokni and Morteza Zadimoghaddam. 2019. Submodular maximization with optimal approximation adaptivity and query complexity. SODA.","DOI":"10.1137\/1.9781611975482.17"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Martin Gr\u00f6tschel L\u00e1szl\u00f3 Lov\u00e1sz and Alexander Schrijver. 1988. Geometric algorithms and combinatorial optimization.  Martin Gr\u00f6tschel L\u00e1szl\u00f3 Lov\u00e1sz and Alexander Schrijver. 1988. Geometric algorithms and combinatorial optimization.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Yassine Hamoudi Patrick Rebentrost Ansis Rosmanis and Miklos Santha. 2019. Quantum and Classical Algorithms for Approximate Submodular Function Minimization. arXiv preprint arXiv:1907.05378.  Yassine Hamoudi Patrick Rebentrost Ansis Rosmanis and Miklos Santha. 2019. Quantum and Classical Algorithms for Approximate Submodular Function Minimization. arXiv preprint arXiv:1907.05378.","DOI":"10.26421\/QIC19.15-16-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2072"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_3_2_1_27_1","unstructured":"Stefanie Jegelka Francis Bach and Suvrit Sra. 2013. Reflection methods for user-friendly submodular optimization. In Advances in Neural Information Processing Systems. 1313\u20131321.  Stefanie Jegelka Francis Bach and Suvrit Sra. 2013. Reflection methods for user-friendly submodular optimization. In Advances in Neural Information Processing Systems. 1313\u20131321."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995589"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.217"},{"volume-title":"Computer Vision","author":"Kohli Pushmeet","key":"e_1_3_2_1_30_1","unstructured":"Pushmeet Kohli and Philip HS Torr . 2010. Dynamic graph cuts and their applications in computer vision . In Computer Vision . Springer , 51\u2013108. Pushmeet Kohli and Philip HS Torr. 2010. Dynamic graph cuts and their applications in computer vision. In Computer Vision. Springer, 51\u2013108."},{"key":"e_1_3_2_1_31_1","unstructured":"Simon Lacoste-Julien and Martin Jaggi. 2015. On the global linear convergence of Frank-Wolfe optimization variants. In Advances in Neural Information Processing Systems. 496\u2013504.  Simon Lacoste-Julien and Martin Jaggi. 2015. On the global linear convergence of Frank-Wolfe optimization variants. In Advances in Neural Information Processing Systems. 496\u2013504."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_1_33_1","volume-title":"NIPS workshop on Discrete Optimization in Machine Learning.","author":"Lin Hui","year":"2010","unstructured":"Hui Lin and Jeff Bilmes . 2010 . An application of the submodular principal partition to training data subset selection . In NIPS workshop on Discrete Optimization in Machine Learning. Hui Lin and Jeff Bilmes. 2010. An application of the submodular principal partition to training data subset selection. In NIPS workshop on Discrete Optimization in Machine Learning."},{"key":"e_1_3_2_1_34_1","volume-title":"Twelfth Annual Conference of the International Speech Communication Association.","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff Bilmes . 2011 . Optimal selection of limited vocabulary speech corpora . In Twelfth Annual Conference of the International Speech Communication Association. Hui Lin and Jeff Bilmes. 2011. Optimal selection of limited vocabulary speech corpora. In Twelfth Annual Conference of the International Speech Communication Association."},{"volume-title":"Mathematical Programming The State of the Art","author":"Lov\u00e1sz L\u00e1szl\u00f3","key":"e_1_3_2_1_35_1","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1983. Submodular functions and convexity . In Mathematical Programming The State of the Art . Springer , 235\u2013257. L\u00e1szl\u00f3 Lov\u00e1sz. 1983. Submodular functions and convexity. In Mathematical Programming The State of the Art. Springer, 235\u2013257."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1025"},{"key":"e_1_3_2_1_37_1","unstructured":"Kevin Scaman Francis Bach S\u00e9bastien Bubeck Laurent Massouli\u00e9 and Yin Tat Lee. 2018. Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems. 2740\u20132749.  Kevin Scaman Francis Bach S\u00e9bastien Bubeck Laurent Massouli\u00e9 and Yin Tat Lee. 2018. Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems. 2740\u20132749."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"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.3384287","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":38,"alternative-id":["10.1145\/3357713.3384287","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384287","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"}}]}}