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: 1998
Venue: PODS
Year: 2026
Pagerank: 4.1905499e-05
Overall Rank: 10,008 | 30.45%
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
449	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00022914472

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,170	Set Cover in the One-pass Edge-arrival Streaming Model	2023	PODS	4.1905499e-05
3,391	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1427968e-05
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
5,064	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.716891e-05
11,841	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1905499e-05
11,831	Variability in Data Streams	2016	PODS	4.1905499e-05
10,905	Streaming Algorithms with Few State Changes	2024	PODS	4.1905499e-05
11,334	The White-Box Adversarial Data Stream Model	2022	PODS	4.1905499e-05
4,399	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2134435e-05