{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T10:58:58Z","timestamp":1770461938246,"version":"3.49.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:00:00Z","timestamp":1669248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1595\/19, 993\/17 and 1871\/19"],"award-info":[{"award-number":["1595\/19, 993\/17 and 1871\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100011643","name":"Blavatnik family foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100011643","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation program","award":["882396"],"award-info":[{"award-number":["882396"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            A streaming algorithm is said to be\n            <jats:italic>adversarially robust<\/jats:italic>\n            if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an\n            <jats:italic>adaptive adversary<\/jats:italic>\n            . We establish a connection between adversarial robustness of streaming algorithms and the notion of\n            <jats:italic>differential privacy<\/jats:italic>\n            . This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.\n          <\/jats:p>","DOI":"10.1145\/3556972","type":"journal-article","created":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T12:31:58Z","timestamp":1660653118000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Adversarially Robust Streaming Algorithms via Differential Privacy"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-344X","authenticated-orcid":false,"given":"Avinatan","family":"Hassidim","sequence":"first","affiliation":[{"name":"Bar-Ilan University and Google, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9586-8002","authenticated-orcid":false,"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Tel Aviv University and Google, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6891-2645","authenticated-orcid":false,"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University and Google, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3960-6002","authenticated-orcid":false,"given":"Yossi","family":"Matias","sequence":"additional","affiliation":[{"name":"Google, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7584-8768","authenticated-orcid":false,"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[{"name":"Tel Aviv University and Google, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,24]]},"reference":[{"key":"e_1_3_5_2_2"},{"key":"e_1_3_5_3_2"},{"key":"e_1_3_5_4_2"},{"key":"e_1_3_5_5_2","article-title":"A framework for adversarial streaming via differential privacy and difference estimators","volume":"2107","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. https:\/\/arxiv.org\/abs\/2107.14527.","journal-title":"CoRR"},{"key":"e_1_3_5_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_3_5_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897566"},{"key":"e_1_3_5_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00084"},{"key":"e_1_3_5_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_26"},{"key":"e_1_3_5_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.15"},{"key":"e_1_3_5_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498334"},{"key":"e_1_3_5_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_3_5_13_2","first-page":"Article 32, 13","volume-title":"Proceedings of APPROX\/RANDOM","author":"Blasiok Jaroslaw","year":"2017","unstructured":"Jaroslaw Blasiok, Jian Ding, and Jelani Nelson. 2017. Continuous monitoring of l_p norms in data streams. In Proceedings of APPROX\/RANDOM. Article 32, 13 pages."},{"key":"e_1_3_5_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188946"},{"key":"e_1_3_5_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"e_1_3_5_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_5_17_2"},{"key":"e_1_3_5_18_2"},{"key":"e_1_3_5_19_2"},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746580"},{"key":"e_1_3_5_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_5_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_3_5_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_3_5_24_2"},{"key":"e_1_3_5_25_2"},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2012.6181772"},{"key":"e_1_3_5_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/SSP.2012.6319752"},{"key":"e_1_3_5_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_3_5_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.55"},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_3_5_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060621"},{"key":"e_1_3_5_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_3_5_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.93"},{"key":"e_1_3_5_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_5_35_2","first-page":"2263","volume-title":"Proceedings of COLT","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 COLT. 2263\u20132285."},{"key":"e_1_3_5_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84252-9_4"},{"key":"e_1_3_5_37_2","article-title":"Accessing data while preserving privacy","volume":"1706","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.http:\/\/arxiv.org\/abs\/1706.01552.","journal-title":"CoRR"},{"key":"e_1_3_5_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"e_1_3_5_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_5_40_2"},{"key":"e_1_3_5_41_2"},{"key":"e_1_3_5_42_2","volume-title":"Sketching and Streaming Algorithms","author":"Nelson Jelani","year":"2011","unstructured":"Jelani Nelson. 2011. Sketching and Streaming Algorithms. Ph. D. Dissertation. Massachusetts Institute of Technology, Cambridge, MA. http:\/\/hdl.handle.net\/1721.1\/66314."},{"key":"e_1_3_5_43_2","first-page":"6402","volume-title":"Proceedings of NeurIPS","author":"Nissim Kobbi","year":"2018","unstructured":"Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. 2018. The limits of post-selection generalization. In Proceedings of NeurIPS. 6402\u20136411."},{"key":"e_1_3_5_44_2"},{"key":"e_1_3_5_45_2","first-page":"1588","volume-title":"Proceedings of COLT","author":"Steinke Thomas","year":"2015","unstructured":"Thomas Steinke and Jonathan Ullman. 2015. Interactive fingerprinting codes and the hardness of preventing false discovery. In Proceedings of COLT. 1588\u20131628."},{"key":"e_1_3_5_46_2","volume-title":"Individuals and Privacy in the Eye of Data Analysis","author":"Stemmer Uri","year":"2016","unstructured":"Uri Stemmer. 2016. Individuals and Privacy in the Eye of Data Analysis. Ph. D. Dissertation. Ben-Gurion University of the Negev."},{"key":"e_1_3_5_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00116"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556972","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3556972","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:52Z","timestamp":1750286932000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556972"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,24]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3556972"],"URL":"https:\/\/doi.org\/10.1145\/3556972","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,24]]},"assertion":[{"value":"2021-06-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}