{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T23:00:31Z","timestamp":1766012431308,"version":"build-2065373602"},"publisher-location":"New York, NY, USA","reference-count":44,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316376","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"114-125","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Dynamic set cover: improved algorithms and lower bounds"],"prefix":"10.1145","author":[{"given":"Amir","family":"Abboud","sequence":"first","affiliation":[{"name":"IBM Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghavendra","family":"Addanki","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barna","family":"Saha","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Distributed PCP Theorems for Hardness of Approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Abboud Amir","year":"2017","unstructured":"Amir Abboud , Aviad Rubinstein , and R. Ryan Williams . 2017 . Distributed PCP Theorems for Hardness of Approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , Berkeley, CA, USA , October 15-17, 2017 . 25\u201336. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. 2017. Distributed PCP Theorems for Hardness of Approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. 25\u201336."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science (FOCS). 434\u2013443.  Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science (FOCS). 434\u2013443.","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050987"},{"key":"e_1_3_2_1_4_1","unstructured":"Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017.  Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017."},{"volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440\u2013452","author":"Fully","key":"e_1_3_2_1_5_1","unstructured":"Fully dynamic all-pairs shortest paths with worst-case update-time revisited . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440\u2013452 . Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440\u2013452."},{"key":"e_1_3_2_1_6_1","unstructured":"Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017.  Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017."},{"volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440\u2013452","author":"Fully","key":"e_1_3_2_1_7_1","unstructured":"Fully dynamic all-pairs shortest paths with worst-case update-time revisited . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440\u2013452 . Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440\u2013452."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175460"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914140"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_1_13_1","unstructured":"Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger and Danupon Nanongkai. 2018.  Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger and Danupon Nanongkai. 2018."},{"volume-title":"Algorithms for Graph Coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1\u201320","author":"Dynamic","key":"e_1_3_2_1_14_1","unstructured":"Dynamic Algorithms for Graph Coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1\u201320 . Dynamic Algorithms for Graph Coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1\u201320."},{"volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Bhattacharya Sayan","key":"e_1_3_2_1_15_1","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Giuseppe F Italiano . 2015. Design of dynamic algorithms via primal-dual method . In International Colloquium on Automata, Languages, and Programming . Springer , 206\u2013218. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano. 2015. Design of dynamic algorithms via primal-dual method. In International Colloquium on Automata, Languages, and Programming. Springer, 206\u2013218."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722183"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_18_1","volume-title":"Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis.","author":"Chechik Shiri","year":"2016","unstructured":"Shiri Chechik , Thomas Dueholm Hansen , Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis. 2016 . Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis. 2016."},{"key":"e_1_3_2_1_19_1","volume-title":"Total Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Single-Source Reachability Decremental","year":"2016","unstructured":"Decremental Single-Source Reachability and Strongly Connected Components in \u00d5(m \u221a n) Total Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 , 9-11 October 2016 , Hyatt Regency, New Brunswick, New Jersey, USA. 315\u2013324. Decremental Single-Source Reachability and Strongly Connected Components in \u00d5(m \u221a n) Total Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. 315\u2013324."},{"key":"e_1_3_2_1_20_1","unstructured":"Lijie Chen. 2018.  Lijie Chen. 2018."},{"key":"e_1_3_2_1_21_1","volume-title":"The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In 33rd Computational Complexity Conference, CCC 2018","author":"On","year":"2018","unstructured":"On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In 33rd Computational Complexity Conference, CCC 2018 , June 22-24, 2018 , San Diego, CA, USA. 14:1\u201314:45. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA. 14:1\u201314:45."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055493"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_32_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"81","author":"Indyk Piotr","year":"2017","unstructured":"Piotr Indyk , Sepideh Mahabadi , Ronitt Rubinfeld , Jonathan Ullman , Ali Vakilian , and Anak Yodpinyanee . 2017 . Fractional set cover in the streaming model . In LIPIcs-Leibniz International Proceedings in Informatics , Vol. 81 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee. 2017. Fractional set cover in the streaming model. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 81. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_33_1","unstructured":"Giuseppe F. Italiano Adam Karczmarz Jakub Lacki and Piotr Sankowski. 2017.  Giuseppe F. Italiano Adam Karczmarz Jakub Lacki and Piotr Sankowski. 2017."},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC","author":"Decremental","year":"2017","unstructured":"Decremental single-source reachability in planar digraphs . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC , Canada , June 19-23, 2017 . 1108\u20131121. Decremental single-source reachability in planar digraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. 1108\u20131121."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884524"},{"key":"e_1_3_2_1_37_1","unstructured":"Andrew McGregor and Hoa T Vu. 2016.  Andrew McGregor and Hoa T Vu. 2016."},{"key":"e_1_3_2_1_38_1","volume-title":"arXiv preprint arXiv:1610.06199","author":"Better","year":"2016","unstructured":"Better streaming algorithms for the maximum coverage problem. arXiv preprint arXiv:1610.06199 ( 2016 ). Better streaming algorithms for the maximum coverage problem. arXiv preprint arXiv:1610.06199 (2016)."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700206"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_41_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Onak Krzysztof","year":"2018","unstructured":"Krzysztof Onak , Baruch Schieber , Shay Solomon , and Nicole Wein . 2018 . Fully Dynamic MIS in Uniformly Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018, Prague, Czech Republic. 92:1\u201392:14. Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. 2018. Fully Dynamic MIS in Uniformly Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. 92:1\u201392:14."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"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.3316376","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":44,"alternative-id":["10.1145\/3313276.3316376","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316376","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"}}]}}