On the Relationship between Lower Bound Methods in Communication Complexity

Communication complexity studies the minimum number of bits distributed parties must communicate in order to perform some joint computation. In the restricted model of communication complexity, unconditional lower bounds can be proven, leading to hardness results for many other problems of interest in computer science. Over the past few decades, numerous lower bound methods have been introduced. Present work aims to unify these lower bounds through linear programming and characterize the relationship between them. In this talk, we discuss ongoing work that aims to investigate the relationship between the three most powerful of these methods, the partition bound, the relaxed partition bound, and the relative discrepancy bound.

This talk is based on work done this summer by Jiahui Liu and Prayaag Venkat, under the guidance of Penghui Yao and Andrew Childs.