Reproduce “A Framework for Adversarially Robust Streaming Algorithms” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev
This work develops generic frameworks for designing adversarially robust randomized streaming algorithms, which preserve accuracy even when an adversary adaptively influences the input stream. The authors provide robust algorithms for various fundamental problems like Fp-estimation, distinct elements, and heavy hitters in insertion-only models, with space complexities comparable to their non-robust counterparts, and demonstrate an attack proving the non-robustness of the classical AMS sketch.
Key insights
- Many functions estimated in insertion-only streaming models, such as Fp norms and distinct elements, exhibit a small 'flip number,' indicating that their values change significantly only a limited number of times over a stream.
- By designing algorithms that control the frequency of public outputs (smoothing) and employing techniques like re-randomization or operating with extremely high internal robustness, it is possible to transform non-robust static streaming algorithms into adversarially robust ones.
- The classical Alon-Matias-Szegedy (AMS) sketch is not robust against adaptive adversaries even in the insertion-only model, highlighting the fragility of common sketching techniques and underscoring the need for new robust designs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.