Collection 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme
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?
Appears in collection : 2016 - T1 - Nexus of information and computation theory
Organizer(s) Green Larsen, Kasper ; Hassibi, Babak ; Kerenidis, Iordanis ; Yeung, Raymond
Date(s) 15/02/2016 - 26/02/2016
linked URL https://web.archive.org/web/20221228152146/http://iss.bu.edu/bobak/csnexus//inequalities.html