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.