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: 1997
Venue: PODS
Year: 2026
Pagerank: 4.1945683e-05
Overall Rank: 10,008 | 30.38%
DOI: 10.1145/3767718

Incoming Non-self Citations Over Time

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

Authors

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
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,167	Set Cover in the One-pass Edge-arrival Streaming Model	2023	PODS	4.1945683e-05
3,385	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1580391e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
5,066	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.7223891e-05
11,833	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1945683e-05
11,823	Variability in Data Streams	2016	PODS	4.1945683e-05
10,901	Streaming Algorithms with Few State Changes	2024	PODS	4.1945683e-05
11,332	The White-Box Adversarial Data Stream Model	2022	PODS	4.1945683e-05
4,403	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2194225e-05