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.3241505e-05
Overall Rank: 5,792 | 59.75%
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,713	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS	6.8182579e-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,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,458	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	4.5013189e-05
13,384	Computational Thinking, Inferential Thinking and "Big Data"	2015	PODS	-
1,096	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.00014088686
8,240	Machine Models and Lower Bounds for Query Processing	2007	PODS	4.5471173e-05
3,782	Bag Query Containment and Information Theory	2020	PODS	6.7691169e-05
14,317	Information Theoretic Aspects Of Data Bases	1983	PODS	-
4,906	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	5.8369374e-05
13,496	Theory of Data Stream Computing: Where to Go	2011	PODS	-
11,909	Compact Summaries over Large Datasets	2015	PODS	4.1905499e-05
12,363	Information Theory For Data Management	2009	VLDB	4.1905499e-05