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.
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.