The White-Box Adversarial Data Stream Model

Summary: Defines the white-box adversarial streaming model, where the adversary observes the full internal state at every step. Key results: randomized L1-heavy hitters beating Misra-Gries on long streams; cryptographic memory reductions; and lower bounds via two-player communication, revealing a separation between bounded and unbounded adversaries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6565d5460db78705
Venue: PODS
Year: 2022
Pagerank: 4.9793485e-05
Overall Rank: 11,840 | 20.40%
DOI: 10.1145/3517804.3526228

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Miklós Ajtai (Hungarian Academy of Sciences)
2. Vladimir Braverman (Google)
3. T.S. Jayram (Lawrence Livermore National Laboratory)
4. Sandeep Silwal (Massachusetts Institute of Technology)
5. Alec Sun (Carnegie Mellon University)
6. David P. Woodruff (Carnegie Mellon University)
7. Samson Zhou (Carnegie Mellon University)

BibTeX Citation

@inproceedings{ajtai_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{The White-Box Adversarial Data Stream Model}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3526228},
        doi = {10.1145/3517804.3526228},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ajtai, Miklós and Braverman, Vladimir and Jayram, T.S. and Silwal, Sandeep and Sun, Alec and Woodruff, David P. and Zhou, Samson},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001832766
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
655	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.00015070228
2,233	Multi-Dimensional Clustering: A New Data Layout Scheme in DB2	2003	SIGMOD	8.7931449e-05
3,050	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.7067158e-05
3,211	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.536045e-05
4,305	The Adversarial Robustness of Sampling	2020	PODS	6.67672e-05
4,381	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.6265793e-05
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,849	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
2	11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS
3	12,321	Variability in Data Streams	2016	PODS
4	7,016	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS
5	11,471	Streaming Algorithms with Few State Changes	2024	PODS
6	9,238	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS
7	4,305	The Adversarial Robustness of Sampling	2020	PODS
8	5,778	Data Streams with Bounded Deletions	2018	PODS
9	10,397	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS
10	4,381	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS