Room 327

Data structure lower bounds using communication complexity

Jayakrishnan M

In this talk, we shall show how asymmetric communication complexity can be applied to prove lower bounds for data structure problems in the cell-probe model. Asymmetric communication complexity, introduced by Miltersen, Nisan, Safra and Wigderson, involves a two party communication model where the input size of the two players differ significantly. Traditional communication complexity has focussed primarily on the total number of bits exchanged in the communication, but we study trade-offs between the number of bits sent by individual players. We show such trade-offs are closely related to the complexity of data structure problems in the cell-probe model. Specifically, we derive a generally applicable method for proving lower bounds in the cell-probe model and show its applications. This is based on the works of Mihai Pătrașcu.