RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

On the Relationship between Lower Bound Methods in Communication Complexity

August 10, 2017 - 1:30pm
Speaker: 
Jiahui Liu & Prayaag Venkat
Institution: 
Columbia University & UMD

*This is a REU final presentation for QuICS*

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.

CSS 3100A