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.6265793e-05
Overall Rank: 4,381 | 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,900	Adore: Differentially Oblivious Relational Database Operators	2023	VLDB	6.9344494e-05
4,305	The Adversarial Robustness of Sampling	2020	PODS	6.67672e-05
7,239	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	5.5782302e-05
9,238	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	5.2056825e-05
10,375	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	4.9793485e-05
11,088	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	4.9793485e-05
11,089	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.9793485e-05
11,471	Streaming Algorithms with Few State Changes	2024	PODS	4.9793485e-05
11,691	Applications of Sketching and Pathways to Impact	2023	PODS	4.9793485e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-05
11,840	The White-Box Adversarial Data Stream Model	2022	PODS	4.9793485e-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
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017387321
1,169	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011726145
4,305	The Adversarial Robustness of Sampling	2020	PODS	6.67672e-05
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05
6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7998727e-05

Semantically Similar Papers

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