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
Jiahui Liu & Prayaag Venkat
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

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to