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)

Paper ID: hd91f6b705030a94b
Venue: PODS
Year: 2020
Pagerank: 6.6234423e-05
Overall Rank: 4,383 | 70.55%
DOI: 10.1145/3375395.3387658

Incoming Non-self Citations Over Time

Authors

1. Omri Ben-Eliezer (Tel Aviv University)
2. Rajesh Jayaram (Carnegie Mellon University)
3. David P. Woodruff (Carnegie Mellon University)
4. Eylon Yogev (Boston University; Tel Aviv University)

BibTeX Citation

@inproceedings{beneliezer_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{A Framework for Adversarially Robust Streaming Algorithms}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387658},
        doi = {10.1145/3375395.3387658},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ben-Eliezer, Omri and Jayaram, Rajesh and Woodruff, David P. and Yogev, Eylon},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,902	Adore: Differentially Oblivious Relational Database Operators	2023	VLDB	6.9311667e-05
4,306	The Adversarial Robustness of Sampling	2020	PODS	6.6735594e-05
7,242	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	5.5755895e-05
9,248	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	5.2032182e-05
10,387	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	4.9769913e-05
11,097	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	4.9769913e-05
11,098	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.9769913e-05
11,477	Streaming Algorithms with Few State Changes	2024	PODS	4.9769913e-05
11,697	Applications of Sketching and Pathways to Impact	2023	PODS	4.9769913e-05
11,834	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9769913e-05
11,846	The White-Box Adversarial Data Stream Model	2022	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
490	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017433989
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017379171
1,170	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011720594
4,306	The Adversarial Robustness of Sampling	2020	PODS	6.6735594e-05
5,780	Data Streams with Bounded Deletions	2018	PODS	5.9949139e-05
6,398	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7971271e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,573	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
2	4,566	Relative Error Streaming Quantiles	2021	PODS
3	11,477	Streaming Algorithms with Few State Changes	2024	PODS
4	11,103	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS
5	5,780	Data Streams with Bounded Deletions	2018	PODS
6	9,248	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS
7	10,409	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS
8	12,335	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
9	11,846	The White-Box Adversarial Data Stream Model	2022	PODS
10	4,306	The Adversarial Robustness of Sampling	2020	PODS