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.9769913e-05
Overall Rank: 11,846 | 20.39%
DOI: 10.1145/3517804.3526228
PDF: Download (CC BY 4.0)

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,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

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.0023943337
335	The Aqua Approximate Query Answering System	1999	SIGMOD	0.000206533
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001831946
490	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017433989
656	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.0001506436
2,234	Multi-Dimensional Clustering: A New Data Layout Scheme in DB2	2003	SIGMOD	8.7892036e-05
3,054	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.7030675e-05
3,212	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.5324957e-05
4,306	The Adversarial Robustness of Sampling	2020	PODS	6.6735594e-05
4,383	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.6234423e-05
5,780	Data Streams with Bounded Deletions	2018	PODS	5.9949139e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,951	Frequent Elements with Witnesses in Data Streams	2021	PODS
2	7,853	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
3	12,327	Variability in Data Streams	2016	PODS
4	7,017	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS
5	11,477	Streaming Algorithms with Few State Changes	2024	PODS
6	9,248	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS
7	4,306	The Adversarial Robustness of Sampling	2020	PODS
8	5,780	Data Streams with Bounded Deletions	2018	PODS
9	10,409	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS
10	4,383	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS