{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:36:16Z","timestamp":1755999376806,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":67,"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.3520064","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1671-1684","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds"],"prefix":"10.1145","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel \/ Google Research, Israel"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel \/ Google Research, Israel"}]},{"given":"Kobbi","family":"Nissim","sequence":"additional","affiliation":[{"name":"Georgetown University, USA"}]},{"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}]},{"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel \/ Google Research, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.44"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_3_2_1_3_1","volume-title":"A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. CoRR, abs\/2107.14527","author":"Attias Idan","year":"2021","unstructured":"Idan Attias , Edith Cohen , Moshe Shechner , and Uri Stemmer . 2021. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. CoRR, abs\/2107.14527 ( 2021 ). Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. 2021. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. CoRR, abs\/2107.14527 (2021)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.679"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1103646"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch52"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106158"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00084"},{"key":"e_1_3_2_1_11_1","volume-title":"Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds. CoRR, abs\/2111.03980","author":"Beimel Amos","year":"2021","unstructured":"Amos Beimel , Haim Kaplan , Yishay Mansour , Kobbi Nissim , Thatchaphol Saranurak , and Uri Stemmer . 2021. Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds. CoRR, abs\/2111.03980 ( 2021 ), arXiv:2111.03980. arxiv:2111.03980 Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. 2021. Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds. CoRR, abs\/2111.03980 (2021), arXiv:2111.03980. arxiv:2111.03980"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a001"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_1_14_1","volume-title":"Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR, abs\/2109.03785","author":"Ben-Eliezer Omri","year":"2021","unstructured":"Omri Ben-Eliezer , Talya Eden , and Krzysztof Onak . 2021. Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR, abs\/2109.03785 ( 2021 ). Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. 2021. Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR, abs\/2109.03785 (2021)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387658"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP) (LIPIcs","volume":"14","author":"Bernstein Aaron","year":"2017","unstructured":"Aaron Bernstein . 2017 . Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs . In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP) (LIPIcs , Vol. 80). 44:1\u201344: 14 . Aaron Bernstein. 2017. Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP) (LIPIcs, Vol. 80). 44:1\u201344:14."},{"key":"e_1_3_2_1_17_1","volume-title":"Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun.","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein , Jan van den Brand , Maximilian Probst Gutenberg , Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020 . Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432. Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.29"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316335"},{"key":"e_1_3_2_1_21_1","volume-title":"Italiano","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Giuseppe F . Italiano . 2015 . Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. 2015. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA). 470\u2013489","author":"Bhattacharya Sayan","year":"2017","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Danupon Nanongkai . 2017 . Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log^ 3 n) Worst Case Update Time . In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA). 470\u2013489 . Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. 2017. Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log^ 3 n) Worst Case Update Time. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA). 470\u2013489."},{"key":"e_1_3_2_1_24_1","unstructured":"Sayan Bhattacharya and Peter Kiss. 2021. Deterministic Rounding of Dynamic Fractional Matchings. arXiv preprint arXiv:2105.01615.  Sayan Bhattacharya and Peter Kiss. 2021. Deterministic Rounding of Dynamic Fractional Matchings. arXiv preprint arXiv:2105.01615."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.113"},{"key":"e_1_3_2_1_26_1","unstructured":"Vladimir Braverman Avinatan Hassidim Yossi Matias Mariano Schain Sandeep Silwal and Samson Zhou. 2021. Adversarial Robustness of Streaming Algorithms through Importance Sampling. arXiv preprint arXiv:2106.14952.  Vladimir Braverman Avinatan Hassidim Yossi Matias Mariano Schain Sandeep Silwal and Samson Zhou. 2021. Adversarial Robustness of Streaming Algorithms through Importance Sampling. arXiv preprint arXiv:2106.14952."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"e_1_3_2_1_28_1","volume-title":"Revisited. In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC). 209\u2013218","author":"Canetti Ran","year":"1998","unstructured":"Ran Canetti , Oded Goldreich , and Shai Halevi . 1998 . The Random Oracle Methodology , Revisited. In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC). 209\u2013218 . Ran Canetti, Oded Goldreich, and Shai Halevi. 1998. The Random Oracle Methodology, Revisited. In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC). 209\u2013218."},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference, (ITCS) (LIPIcs","volume":"23","author":"Chakrabarti Amit","year":"2022","unstructured":"Amit Chakrabarti , Prantar Ghosh , and Manuel Stoeckl . 2022 . Adversarially Robust Coloring for Graph Streams . In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, (ITCS) (LIPIcs , Vol. 215). 37:1\u201337: 23 . Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. 2022. Adversarially Robust Coloring for Graph Streams. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, (ITCS) (LIPIcs, Vol. 215). 37:1\u201337:23."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00109"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451025"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.147"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316379"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746580"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316381"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.75"},{"key":"e_1_3_2_1_42_1","unstructured":"Varun Gupta Christopher Jung Seth Neel Aaron Roth Saeed Sharifi-Malvajerdi and Chris Waites. 2021. Adaptive Machine Unlearning. arXiv preprint arXiv:2106.04378.  Varun Gupta Christopher Jung Seth Neel Aaron Roth Saeed Sharifi-Malvajerdi and Chris Waites. 2021. Adaptive Machine Unlearning. arXiv preprint arXiv:2106.04378."},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC). 153\u2013166","author":"Gutenberg Maximilian Probst","year":"2020","unstructured":"Maximilian Probst Gutenberg , Virginia Vassilevska Williams , and Nicole Wein . 2020 . New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs . In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC). 153\u2013166 . arxiv:2001.10751 Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. 2020. New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs. In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC). 153\u2013166. arxiv:2001.10751"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.155"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.154"},{"volume-title":"Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS). 454\u2013463","author":"Hardt Moritz","key":"e_1_3_2_1_46_1","unstructured":"Moritz Hardt and Jonathan R. Ullman . 2014. Preventing False Discovery in Interactive Data Analysis Is Hard . In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS). 454\u2013463 . Moritz Hardt and Jonathan R. Ullman. 2014. Preventing False Discovery in Interactive Data Analysis Is Hard. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS). 454\u2013463."},{"key":"e_1_3_2_1_47_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Hassidim Avinatan","year":"2020","unstructured":"Avinatan Hassidim , Haim Kaplan , Yishay Mansour , Yossi Matias , and Uri Stemmer . 2020 . Adversarially Robust Streaming Algorithms via Differential Privacy . In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 . https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/0172d289da48c48de8c5ebf3de9f7ee1-Abstract.html Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/0172d289da48c48de8c5ebf3de9f7ee1-Abstract.html"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.24"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 33rd Conference on Learning Theory, COLT (Proceedings of Machine Learning Research","volume":"2285","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan , Katrina Ligett , Yishay Mansour , Moni Naor , and Uri Stemmer . 2020 . Privately Learning Thresholds: Closing the Exponential Gap . In Proceedings of the 33rd Conference on Learning Theory, COLT (Proceedings of Machine Learning Research , Vol. 125). 2263\u2013 2285 . Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. 2020. Privately Learning Thresholds: Closing the Exponential Gap. In Proceedings of the 33rd Conference on Learning Theory, COLT (Proceedings of Machine Learning Research, Vol. 125). 2263\u20132285."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84252-9_4"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_53_1","volume-title":"Accessing Data while Preserving Privacy. CoRR, abs\/1706.01552","author":"Kellaris Georgios","year":"2017","unstructured":"Georgios Kellaris , George Kollios , Kobbi Nissim , and Adam O\u2019Neill . 2017. Accessing Data while Preserving Privacy. CoRR, abs\/1706.01552 ( 2017 ). Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O\u2019Neill. 2017. Accessing Data while Preserving Privacy. CoRR, abs\/1706.01552 (2017)."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_1_57_1","article-title":"Concentration Bounds for High Sensitivity Functions Through Differential Privacy","volume":"9","author":"Nissim Kobbi","year":"2019","unstructured":"Kobbi Nissim and Uri Stemmer . 2019 . Concentration Bounds for High Sensitivity Functions Through Differential Privacy . J. Priv. Confidentiality , 9 , 1 (2019). Kobbi Nissim and Uri Stemmer. 2019. Concentration Bounds for High Sensitivity Functions Through Differential Privacy. J. Priv. Confidentiality, 9, 1 (2019).","journal-title":"J. Priv. Confidentiality"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118238.3118552"},{"volume-title":"Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Solomon Shay","key":"e_1_3_2_1_60_1","unstructured":"Shay Solomon . [n. d.]. Fully Dynamic Maximal Matching in Constant Update Time . In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS) . IEEE press , 325\u2013334. Shay Solomon. [n. d.]. Fully Dynamic Maximal Matching in Constant Update Time. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE press, 325\u2013334."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.57"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0045-2"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00036"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384258"},{"key":"e_1_3_2_1_66_1","unstructured":"David P Woodruff and Samson Zhou. 2020. Tight bounds for adversarially robust streams and sliding windows via difference estimators. arXiv preprint arXiv:2011.07471.  David P Woodruff and Samson Zhou. 2020. Tight bounds for adversarially robust streams and sliding windows via difference estimators. arXiv preprint arXiv:2011.07471."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"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.3520064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":67,"alternative-id":["10.1145\/3519935.3520064","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520064","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"}}]}}