{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T15:59:49Z","timestamp":1783007989116,"version":"3.54.5"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-18-1-2562"],"award-info":[{"award-number":["N00014-18-1-2562"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CCF-1815840"],"award-info":[{"award-number":["CCF-1815840"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems.<\/jats:p>\n          <jats:p>\n            In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally\n            <jats:italic>\n              F\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            -estimation,\n            <jats:italic>\n              F\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            -heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1+\u03b5)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log\n            <jats:italic>n<\/jats:italic>\n            , 1\/\u03b5) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.\n          <\/jats:p>","DOI":"10.1145\/3498334","type":"journal-article","created":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T17:52:59Z","timestamp":1643651579000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["A Framework for Adversarially Robust Streaming Algorithms"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6366-5964","authenticated-orcid":false,"given":"Omri","family":"Ben-Eliezer","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0332-6332","authenticated-orcid":false,"given":"Rajesh","family":"Jayaram","sequence":"additional","affiliation":[{"name":"Google Research, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8599-2472","authenticated-orcid":false,"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,31]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982465"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_8_2","unstructured":"Idan Attias Edith Cohen Moshe Shechner and Uri Stemmer. 2021. A framework for adversarial streaming via differential privacy and difference estimators.  arXiv:2107.14527. Retrieved from https:\/\/arxiv.org\/abs\/2107.14527."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"Omri Ben-Eliezer Talya Eden and Krzysztof Onak. 2021. Adversarially robust streaming via dense\u2013Sparse trade-offs.  arXiv:2109.03785 (2021). Retrieved from https:\/\/arxiv.org\/abs\/2109.03785.","DOI":"10.1137\/1.9781611977066.15"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.156"},{"key":"e_1_3_2_13_2","first-page":"32:1\u201332:13","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"B\u0142asiok Jaros\u0142aw","year":"2017","unstructured":"Jaros\u0142aw B\u0142asiok, Jian Ding, and Jelani Nelson. 2017. Continuous monitoring of L_p norms in data streams. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 32:1\u201332:13."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034798"},{"key":"e_1_3_2_15_2","unstructured":"Vladimir Braverman Avinatan Hassidim Yossi Matias Mariano Schain Sandeep Silwal and Samson Zhou. 2021. Adversarial robustness of streaming algorithms through importance sampling.  arXiv:2106.14952. Retrieved from https:\/\/arxiv.org\/abs\/2106.14952."},{"key":"e_1_3_2_16_2","unstructured":"Amit Chakrabarti Prantar Ghosh and Manuel Stoeckl. 2021. Adversarially robust coloring for graph streams.  arXiv:2109.11130. Retrieved from https:\/\/arxiv.org\/abs\/2109.11130."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.14"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_2_19_2","first-page":"196","volume-title":"Proceedings of the 16th International Conference on Artificial Intelligence and Statistics","author":"Clifford Peter","year":"2013","unstructured":"Peter Clifford and Ioana Cosma. 2013. A simple sketching algorithm for entropy estimation over streaming data. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics. 196\u2013206."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/645918.672512"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02026-1_28"},{"key":"e_1_3_2_23_2","first-page":"58:1\u201358:15","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","author":"Ganguly Sumit","year":"2018","unstructured":"Sumit Ganguly and David P. Woodruff. 2018. High probability frequency moment sketches. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. 58:1\u201358:15."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2012.6181772"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SSP.2012.6319752"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000001"},{"key":"e_1_3_2_27_2","first-page":"79:1\u201379:25","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference","author":"Goldwasser Shafi","year":"2020","unstructured":"Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff. 2020. Pseudo-deterministic streaming. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 79:1\u201379:25."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1080\/00949658908811160"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4064\/sm-70-3-231-283"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.76"},{"key":"e_1_3_2_32_2","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","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 Proceedings of the Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_33_2","volume-title":"Sketching and Sampling Algorithms for High-Dimensional Data","author":"Jayaram Rajesh","year":"2021","unstructured":"Rajesh Jayaram. 2021. Sketching and Sampling Algorithms for High-Dimensional Data. Ph.D. Dissertation. Carnegie Mellon University, Pittsburgh, PA."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_3_2_35_2","first-page":"29:1\u201329:21","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Jayaram Rajesh","year":"2019","unstructured":"Rajesh Jayaram and David P. Woodruff. 2019. Towards optimal moment estimation in streaming and distributed models. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 29:1\u201329:21."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.82"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384278"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.37"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873694"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84252-9_4"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591812"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_43"},{"key":"e_1_3_2_45_2","first-page":"49","volume-title":"Proceedings of Symposia in Applied Mathematics","volume":"42","author":"McCurley Kevin S.","year":"1990","unstructured":"Kevin S. McCurley. 1990. The discrete logarithm problem. In Proceedings of Symposia in Applied Mathematics, Vol. 42. 49\u201374."},{"key":"e_1_3_2_46_2","unstructured":"Boaz Menuhin and Moni Naor. 2021. Keep that card in mind: Card guessing with limited memory.  arXiv:2107.03885. Retrieved from https:\/\/arxiv.org\/abs\/2107.03885."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/080733772"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_28"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/2512973"},{"key":"e_1_3_2_53_2","first-page":"167","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Woodruff David","year":"2004","unstructured":"David Woodruff. 2004. Optimal space lower bounds for all frequency moments. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. 167\u2013175."},{"key":"e_1_3_2_54_2","unstructured":"David P. Woodruff and Samson Zhou. 2021. Adversarially robust and sliding window streaming algorithms without the overhead.  arXiv:2011.07471. Retrieved from https:\/\/arxiv.org\/abs\/2011.07471."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498334","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:05Z","timestamp":1750188605000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3498334"],"URL":"https:\/\/doi.org\/10.1145\/3498334","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}