{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:41Z","timestamp":1781077721715,"version":"3.54.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100014385","name":"Kreitman School of Advanced Graduate Studies, Ben-Gurion University of the Negev","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100014385","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Vatat Scholarship from the Israeli Council for Higher Education"},{"name":"Lynn and William Frankel Center for Computer Science at Ben-Gurion University"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Len Blavatnik and the Blavatnik Family foundation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing <jats:italic>robust streaming algorithms<\/jats:italic> that provide provable guarantees even when the input stream is chosen adaptively as the execution progresses. We propose a new framework for robust streaming that combines techniques from two recently suggested frameworks by Hassidim et al. (NeurIPS 2020) and by Woodruff and Zhou\u00a0(FOCS 2021). These recently suggested frameworks rely on very different ideas, each with its own strengths and weaknesses. We combine these two frameworks into a single hybrid framework that obtains the \u201cbest of both worlds\u201d, thereby solving a question left open by Woodruff and Zhou.\n<\/jats:p>","DOI":"10.1007\/s00453-024-01259-8","type":"journal-article","created":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T13:02:38Z","timestamp":1725109358000},"page":"3339-3394","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Framework for Adversarial Streaming Via Differential Privacy and Difference Estimators"],"prefix":"10.1007","volume":"86","author":[{"given":"Idan","family":"Attias","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edith","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Shechner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"issue":"1","key":"1259_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"1259_CR2","doi-asserted-by":"publisher","first-page":"1845","DOI":"10.1137\/080733772","volume":"40","author":"I Mironov","year":"2011","unstructured":"Mironov, I., Naor, M., Segev, G.: Sketching in adversarial environments. SIAM J. Comput. 40(6), 1845\u20131870 (2011). https:\/\/doi.org\/10.1137\/080733772","journal-title":"SIAM J. Comput."},{"key":"1259_CR3","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Hemenway, B., Rudra, A., Strauss, M.J., Wootters, M.: Recovering simple signals. In: 2012 Information theory and applications workshop, pp. 382\u2013391 (2012)","DOI":"10.1109\/ITA.2012.6181772"},{"key":"1259_CR4","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Hemenway, B., Strauss, M.J., Woodruff, D.P., Wootters, M.: Reusable low-error compressive sampling schemes through privacy. In: 2012 IEEE statistical signal processing workshop (SSP), pp. 536\u2013539 (2012)","DOI":"10.1109\/SSP.2012.6319752"},{"key":"1259_CR5","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: SODA, pp. 459\u2013467 (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.40","DOI":"10.1137\/1.9781611973099.40"},{"key":"1259_CR6","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS, pp. 5\u201314 (2012). https:\/\/doi.org\/10.1145\/2213556.2213560","DOI":"10.1145\/2213556.2213560"},{"key":"1259_CR7","doi-asserted-by":"crossref","unstructured":"Hardt, M., Woodruff, D.P.: How robust are linear sketches to adaptive inputs? In: STOC, pp. 121\u2013130 (2013)","DOI":"10.1145\/2488608.2488624"},{"key":"1259_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Eliezer, O., Yogev, E.: The adversarial robustness of sampling. In: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, pp. 49\u201362 (2020)","DOI":"10.1145\/3375395.3387643"},{"issue":"2","key":"1259_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3498334","volume":"69","author":"O Ben-Eliezer","year":"2022","unstructured":"Ben-Eliezer, O., Jayaram, R., Woodruff, D.P., Yogev, E.: A framework for adversarially robust streaming algorithms. ACM J. ACM (JACM) 69(2), 1\u201333 (2022)","journal-title":"ACM J. ACM (JACM)"},{"key":"1259_CR10","unstructured":"Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., Stemmer, U.: Adversarially robust streaming algorithms via differential privacy. In: NeurIPS (2020)"},{"key":"1259_CR11","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Mansour, Y., Nissim, K., Stemmer, U.: Separating adaptive streaming from oblivious streaming using the bounded storage model. In: CRYPTO 2021 (2021). arxiv: 2101.10836","DOI":"10.1007\/978-3-030-84252-9_4"},{"key":"1259_CR12","first-page":"3544","volume":"34","author":"V Braverman","year":"2021","unstructured":"Braverman, V., Hassidim, A., Matias, Y., Schain, M., Silwal, S., Zhou, S.: Adversarial robustness of streaming algorithms through importance sampling. Adv. Neural. Inf. Process. Syst. 34, 3544\u20133557 (2021)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1259_CR13","unstructured":"Cohen, E., Lyu, X., Nelson, J., Sarl\u00f3s, T., Shechner, M., Stemmer, U.: On the robustness of countsketch to adaptive inputs. In: International conference on machine learning, pp. 4112\u20134140 (2022). PMLR"},{"key":"1259_CR14","doi-asserted-by":"crossref","unstructured":"Cohen, E., Nelson, J., Sarl\u00f3s, T., Stemmer, U.: Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs. In: Proceedings of the AAAI conference on artificial intelligence, 37, 7235\u20137243 (2023)","DOI":"10.1609\/aaai.v37i6.25882"},{"key":"1259_CR15","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Theory of Cryptography Conference, pp. 265\u2013284 (2006). Springer","DOI":"10.1007\/11681878_14"},{"key":"1259_CR16","unstructured":"Woodruff, D.P., Zhou, S.: Tight bounds for adversarially robust streams and sliding windows via difference estimators. In: FOCS (2021)"},{"key":"1259_CR17","doi-asserted-by":"crossref","unstructured":"Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A.L.: Preserving statistical validity in adaptive data analysis. In: Proceedings of the forty-seventh annual ACM symposium on theory of computing, pp. 117\u2013126 (2015)","DOI":"10.1145\/2746539.2746580"},{"key":"1259_CR18","doi-asserted-by":"crossref","unstructured":"Bassily, R., Nissim, K., Smith, A.D., Steinke, T., Stemmer, U., Ullman, J.R.: Algorithmic stability for adaptive data analysis. SIAM J. Comput. 50(3) (2021)","DOI":"10.1137\/16M1103646"},{"key":"1259_CR19","doi-asserted-by":"crossref","unstructured":"Jung, C., Ligett, K., Neel, S., Roth, A., Sharifi-Malvajerdi, S., Shenfeld, M.: A new analysis of differential privacy\u2019s generalization guarantees. In: 11th innovations in theoretical computer science conference (ITCS 2020) (2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","DOI":"10.1145\/3406325.3465358"},{"key":"1259_CR20","doi-asserted-by":"crossref","unstructured":"Hardt, M., Ullman, J.: Preventing false discovery in interactive data analysis is hard. In: 2014 IEEE 55th annual symposium on foundations of computer science, pp. 454\u2013463 (2014). IEEE","DOI":"10.1109\/FOCS.2014.55"},{"key":"1259_CR21","unstructured":"Steinke, T., Ullman, J.: Interactive fingerprinting codes and the hardness of preventing false discovery. In: Conference on learning theory, pp. 1588\u20131628 (2015). PMLR"},{"key":"1259_CR22","unstructured":"Nissim, K., Smith, A.D., Steinke, T., Stemmer, U., Ullman, J.: The limits of post-selection generalization. In: NeurIPS, pp. 6402\u20136411 (2018)"},{"key":"1259_CR23","doi-asserted-by":"crossref","unstructured":"Nissim, K., Stemmer, U.: Concentration bounds for high sensitivity functions through differential privacy. J. Priv. Confidentiality 9(1) (2019)","DOI":"10.29012\/jpc.658"},{"key":"1259_CR24","unstructured":"Shenfeld, M., Ligett, K.: A necessary and sufficient stability notion for adaptive generalization. In: NeurIPS, pp. 11481\u201311490 (2019)"},{"key":"1259_CR25","unstructured":"Shenfeld, M., Ligett, K.: Generalization in the face of adaptivity: a bayesian perspective. CoRR arXiv: 2106.10761 (2021)"},{"key":"1259_CR26","unstructured":"Kontorovich, A., Sadigurschi, M., Stemmer, U.: Adaptive data analysis with correlated observations. In: International conference on machine learning, pp. 11483\u201311498 (2022). PMLR"},{"key":"1259_CR27","unstructured":"Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi-Malvajerdi, S., Waites, C.: Adaptive machine unlearning. arXiv preprint arXiv:2106.04378 (2021)"},{"key":"1259_CR28","doi-asserted-by":"crossref","unstructured":"Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., Stemmer, U.: Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. CoRR arXiv: 2111.03980 (2021)","DOI":"10.1145\/3519935.3520064"},{"key":"1259_CR29","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: Proceedings of the forty-first annual ACM symposium on theory of computing, pp. 381\u2013390 (2009)","DOI":"10.1145\/1536414.1536467"},{"key":"1259_CR30","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.N.: A multiplicative weights mechanism for privacy-preserving data analysis. In: 2010 IEEE 51st annual symposium on foundations of computer science, pp. 61\u201370 (2010). IEEE","DOI":"10.1109\/FOCS.2010.85"},{"issue":"1","key":"1259_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a001","volume":"12","author":"A Beimel","year":"2016","unstructured":"Beimel, A., Nissim, K., Stemmer, U.: Private learning and sanitization: Pure vs. approximate differential privacy. Theory Comput. 12(1), 1\u201361 (2016). https:\/\/doi.org\/10.4086\/toc.2016.v012a001","journal-title":"Theory Comput."},{"key":"1259_CR32","doi-asserted-by":"crossref","unstructured":"Bun, M., Nissim, K., Stemmer, U., Vadhan, S.: Differentially private release and learning of threshold functions. In: 2015 IEEE 56th annual symposium on foundations of computer science, pp. 634\u2013649 (2015). IEEE","DOI":"10.1109\/FOCS.2015.45"},{"key":"1259_CR33","doi-asserted-by":"crossref","unstructured":"Bun, M., Dwork, C., Rothblum, G.N., Steinke, T.: Composable and versatile privacy via truncated cdp. In: Proceedings of the 50th Annual ACM SIGACT symposium on theory of computing, pp. 74\u201386 (2018)","DOI":"10.1145\/3188745.3188946"},{"key":"1259_CR34","unstructured":"Kaplan, H., Ligett, K., Mansour, Y., Naor, M., Stemmer, U.: Privately learning thresholds: Closing the exponential gap. In: Conference on learning theory, pp. 2263\u20132285 (2020). PMLR"},{"key":"1259_CR35","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: Privacy via distributed noise generation. In: Advances in Cryptology-EUROCRYPT 2006: 24th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486\u2013503 (2006). Springer","DOI":"10.1007\/11761679_29"},{"key":"1259_CR36","doi-asserted-by":"crossref","unstructured":"Dwork, C., Lei, J.: Differential privacy and robust statistics. In: Proceedings of the Forty-first Annual ACM symposium on theory of computing, pp. 371\u2013380 (2009)","DOI":"10.1145\/1536414.1536466"},{"key":"1259_CR37","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., Vadhan, S.: Boosting and differential privacy. In: 2010 IEEE 51st annual symposium on foundations of computer science, pp. 51\u201360 (2010). IEEE","DOI":"10.1109\/FOCS.2010.12"},{"key":"1259_CR38","first-page":"615","volume":"4","author":"M Thorup","year":"2004","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. SODA 4, 615\u2013624 (2004)","journal-title":"SODA"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01259-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01259-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01259-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T05:03:54Z","timestamp":1732165434000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01259-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,31]]},"references-count":38,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1259"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01259-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,31]]},"assertion":[{"value":"19 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}