Information Complexity: a Tutorial

Summary: Tutorial on the information-complexity paradigm for proving tight lower bounds in streaming, sketching, sampling and related massive-data models, formalizing how much information about inputs any algorithm must transmit or retain. Connects information theory, statistics, and geometry. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1516
Venue: PODS
Year: 2010
Pagerank: 5.3292726e-05
Overall Rank: 5,782 | 59.78%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. T.S. Jayram

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,708	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS	6.8247903e-05

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
1,472	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011828662

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,371	Computational Thinking, Inferential Thinking and "Big Data"	2015	PODS	-
8,462	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	4.5056381e-05
1,099	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.00014096312
8,241	Machine Models and Lower Bounds for Query Processing	2007	PODS	4.5519176e-05
3,775	Bag Query Containment and Information Theory	2020	PODS	6.775636e-05
14,303	Information Theoretic Aspects Of Data Bases	1983	PODS	-
4,900	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	5.8423536e-05
13,483	Theory of Data Stream Computing: Where to Go	2011	PODS	-
11,901	Compact Summaries over Large Datasets	2015	PODS	4.1945683e-05
12,355	Information Theory For Data Management	2009	VLDB	4.1945683e-05