Representation Obliviousness and Pseudodeterminism in Streaming Algorithms

Summary: Define representation obliviousness for pseudodeterministic streaming algorithms: algorithm's output distribution depends only on the set of distinct elements, not their representation. Prove any representation-oblivious pseudodeterministic F0 estimator needs Ω(n) space (Ω(n/t) for t passes), matching deterministic multi-pass bounds. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 2059
Venue: PODS
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,181 | 30.15%
DOI: 10.1145/3767718

Incoming Non-self Citations Over Time

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

Authors

1. Michael Chen (Iowa State University)
2. Sourav Chakraborty (Indian Statistical Institute)
3. A. Pavan (Iowa State University)
4. N. V. Vinodchandran (University of Nebraska–Lincoln)

BibTeX Citation

@inproceedings{chen_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Representation Obliviousness and Pseudodeterminism in Streaming Algorithms}},
        url = {https://dl.acm.org/doi/10.1145/3767718},
        doi = {10.1145/3767718},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chen, Michael and Chakraborty, Sourav and Pavan, A. and Vinodchandran, N. V.},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,669	Data Streams with Bounded Deletions	2018	PODS
2	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
3	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
4	5,668	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS
5	12,034	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
6	12,026	Variability in Data Streams	2016	PODS
7	10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
8	11,123	Streaming Algorithms with Few State Changes	2024	PODS
9	11,531	The White-Box Adversarial Data Stream Model	2022	PODS
10	4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS