2026-07-23T19:19:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17511 2024-03-06T10:59:46Z ddc:004 open_access

A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators Attias, Idan Cohen, Edith Shechner, Moshe Stemmer, Uri Streaming adversarial robustness differential privacy 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 robust streaming algorithms 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 [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 "best of both worlds", thereby solving a question left open by Woodruff and Zhou. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Idan Attias and Edith Cohen and Moshe Shechner and Uri Stemmer 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.8 urn:nbn:de:0030-drops-175115 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.8 eng https://creativecommons.org/licenses/by/4.0/legalcode