A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
This work addresses the need for more reliable streaming algorithms in adversarial settings, though it is incremental as it builds on prior frameworks.
The paper tackles the problem of designing robust streaming algorithms that provide provable guarantees against adaptively chosen input streams, by proposing a hybrid framework that combines two existing frameworks to achieve the 'best of both worlds' and solve an open question.
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.