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: 1821
Venue: PODS
Year: 2020
Pagerank: 6.7786745e-05
Overall Rank: 4,291 | 70.57%
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,859	Adore: Differentially Oblivious Relational Database Operators	2023	VLDB	7.0670506e-05
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
7,091	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	5.7062634e-05
9,060	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	5.3251649e-05
10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	5.093636e-05
10,645	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	5.093636e-05
10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.093636e-05
11,123	Streaming Algorithms with Few State Changes	2024	PODS	5.093636e-05
11,375	Applications of Sketching and Pathways to Impact	2023	PODS	5.093636e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-05
11,531	The White-Box Adversarial Data Stream Model	2022	PODS	5.093636e-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
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
1,146	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011984702
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05

Semantically Similar Papers

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