Title: Communication Complexity and Data Structure Lower Bounds through an Information Theoretic Lens 

Advisor: Anup Rao

Supervisory Committee: Anup Rao (Chair), Rekha Thomas (GSR, Math), Paul Beame, and Dan Suciu

Abstract: A wide variety of diverse problems in 2-party communication complexity and data structures often have a common information theoretical underpinning to them. In this work, we exploit this further to study the problems of interactive compression of communication protocols and data structure lower bounds for finding the median of a set. 

The question of interactive compression asks if one can compress the communication of a protocol when the information revealed by the players is small. We prove improved bounds on the compression when the information revealed by the players is asymmetric. Asymmetry in the information often arises while simulating data structure algorithms with communication protocols, thus providing a motivation for this study. 

We also initiate the study of finding the median in the cell probe model. The task is to maintain a set of integers, add new elements and query the median. We prove lower bounds on the query time of finding the median when the add operations are non-adaptive. The proof uses a connection to the Sunflower Lemma from combinatorics. To this end, we propose to study the following problems: a) lower bounds for median with adaptive add operations b) threshold phenomenon in data structures for predecessor search.
CSE 303
Monday, November 28, 2016 - 16:00 to 18:00