{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:57Z","timestamp":1766281017424,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2021,6,15]]},"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>","DOI":"10.1145\/3471485.3471488","type":"journal-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T05:22:06Z","timestamp":1623993726000},"page":"6-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Framework for Adversarially Robust Streaming Algorithms"],"prefix":"10.1145","volume":"50","author":[{"given":"Omri","family":"Ben-Eliezer","sequence":"first","affiliation":[{"name":"Harvard University"}]},{"given":"Rajesh","family":"Jayaram","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[{"name":"Boston Univ. &amp; Tel Aviv Univ."}]}],"member":"320","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175461"},{"volume-title":"J. Ding, and J","author":"J.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034798"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.14"},{"key":"e_1_2_1_9_1","first-page":"196","volume-title":"Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, AISTATS","author":"Clifford P.","year":"2013"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645918.672512"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP","author":"Ganguly S.","year":"2018"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2012.6181772"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSP.2012.6319752"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949658908811160"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.76"},{"volume-title":"Advances in Neural Information Processing Systems 33","year":"2020","author":"Hassidim A.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"APPROX\/RANDOM","author":"Jayaram R.","year":"2019"},{"volume-title":"A simple proof of a new set disjointness with applications to data streams","year":"2020","author":"Kamath A.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873694"},{"volume-title":"Separating adaptive streaming from oblivious streaming. CoRR, abs\/2101.10836","year":"2021","author":"Kaplan H.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_43"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733772"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_28"},{"volume-title":"Tight bounds for adversarially robust streams and sliding windows via difference estimators. CoRR, abs\/2011.07471","year":"2020","author":"Woodruff D. P.","key":"e_1_2_1_28_1"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471488","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3471485.3471488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:26Z","timestamp":1750191446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,15]]}},"alternative-id":["10.1145\/3471485.3471488"],"URL":"https:\/\/doi.org\/10.1145\/3471485.3471488","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}