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: 1897
Venue: PODS
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,531 | 20.89%
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
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

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.0024089429
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
654	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.0001527187
2,197	Multi-Dimensional Clustering: A New Data Layout Scheme in DB2	2003	SIGMOD	8.9684812e-05
2,992	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.8836024e-05
3,150	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.7055991e-05
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.7786745e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,698	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
2	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
3	12,026	Variability in Data Streams	2016	PODS
4	6,871	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS
5	11,123	Streaming Algorithms with Few State Changes	2024	PODS
6	9,060	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS
7	4,211	The Adversarial Robustness of Sampling	2020	PODS
8	5,669	Data Streams with Bounded Deletions	2018	PODS
9	10,181	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS
10	4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS