Nexus of Information and Computation Theories
Fundamental Inequalities and Lower Bounds Theme
February 15 – 26, 2016

Titles, Abstracts, and Video Links

Entire YouTube Playlist

Final Schedule

Overview: The area of data structure lower bounds has seen a surge of activity in recent years, thanks to new connections with communication complexity problems. Some of the most promising avenues towards stronger bounds for dynamic data structures seems to require progress in multi-terminal communication complexity.

Canonical Problems: What does it cost to maintain a data structure? What are the fundamental tradeoffs between storage and access efficiency?

Keywords: information inequalities, algorithms, models of computation, data structure lower bounds, distributed storage, entropic vectors.

Theme Organizers