A Framework for Adversarially Robust Streaming Algorithms
Summary: Framework to convert space-efficient randomized insertion-only streaming algorithms into adversarially robust (1+ε)-approx algorithms against adaptively chosen streams. Applies to distinct elements, F_p (estimation/heavy hitters), entropy, matching space of non-robust algorithms up to poly(log n,1/ε) factors via generic transformation tools. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Omri Ben-Eliezer
- 2. Rajesh Jayaram
- 3. David P. Woodruff
- 4. Eylon Yogev
Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,036 | Adore: Differentially Oblivious Relational Database Operators | 2023 | VLDB | 6.5089579e-05 |
| 4,172 | The Adversarial Robustness of Sampling | 2020 | PODS | 6.3879072e-05 |
| 8,130 | Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald | 2024 | PODS | 4.5784634e-05 |
| 8,905 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.427232e-05 |
| 10,351 | On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space | 2025 | PODS | 4.1945683e-05 |
| 10,353 | Perfect Sampling in Turnstile Streams Beyond Small Moments | 2025 | PODS | 4.1945683e-05 |
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |
| 11,169 | Applications of Sketching and Pathways to Impact | 2023 | PODS | 4.1945683e-05 |
| 11,320 | Truly Perfect Samplers for Data Streams and Sliding Windows | 2022 | PODS | 4.1945683e-05 |
| 11,332 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 383 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00024820873 |
| 588 | Practical Skew Handling in Parallel Joins | 1992 | VLDB | 0.00019604754 |
| 1,040 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS | 0.00014488943 |
| 2,884 | BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory | 2017 | PODS | 7.9620506e-05 |
| 4,172 | The Adversarial Robustness of Sampling | 2020 | PODS | 6.3879072e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,823 | Variability in Data Streams | 2016 | PODS | 4.1945683e-05 |
| 6,418 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.0696932e-05 |
| 4,966 | Relative Error Streaming Quantiles | 2021 | PODS | 5.7959749e-05 |
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |
| 10,358 | Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces | 2025 | PODS | 4.1945683e-05 |
| 8,905 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.427232e-05 |
| 10,008 | Representation Obliviousness and Pseudodeterminism in Streaming Algorithms | 2026 | PODS | 4.1945683e-05 |
| 11,833 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD | 4.1945683e-05 |
| 11,332 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 4.1945683e-05 |
| 4,172 | The Adversarial Robustness of Sampling | 2020 | PODS | 6.3879072e-05 |