TY - GEN
T1 - Cell-Probe lower bounds from online communication complexity
AU - Alman, Josh
AU - Wang, Joshua R.
AU - Yu, Huacheng
N1 - Publisher Copyright:
© 2018 Copyright held by the owner/author(s).
PY - 2018/6/20
Y1 - 2018/6/20
N2 - In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures. We first present a tight lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst case O(log n)-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spending o(log n) (even amortized) time per operation results in at best an exp(− 2n) probability of correctly answering a (1/2 +)-fraction of the n queries.
AB - In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures. We first present a tight lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst case O(log n)-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spending o(log n) (even amortized) time per operation results in at best an exp(− 2n) probability of correctly answering a (1/2 +)-fraction of the n queries.
KW - Cell-probe model
KW - Data structure lower bounds
KW - Online communication complexity
UR - http://www.scopus.com/inward/record.url?scp=85049926534&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049926534&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188862
DO - 10.1145/3188745.3188862
M3 - Conference contribution
AN - SCOPUS:85049926534
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 239
EP - 252
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Henzinger, Monika
A2 - Kempe, David
A2 - Diakonikolas, Ilias
PB - Association for Computing Machinery
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -