Does communication complexity versus query complexity follow our natural intuition (in the quantum model)?
COM2 Level 1
Both query and communication complexity are central computation models due to their broad applicability and simplicity. A central problem in communication complexity is computing f(x \XOR y) when Alice and Bob are given x and y, respectively. It is easy to argue that any query algorithm for a Boolean function $f$ in the classical world can be simulated to give a communication protocol (of almost the exact cost) for computing the function f(x \XOR y). This also follows from our intuition that communication should be easier than querying. But does this intuition hold in the quantum world? The answer is NO. And this will show a major conceptual difference between our classical intuition and the quantum world.
Sourav Chakraborty is an Associate Professor in Computer Science at the Indian Statistical Institute, Kolkata, India. He finished his bachelors in Mathematics from Chennai Mathematical Institute in 2003 and then went on to do his Master's (in 2005) and Ph.D. (in 2008) in Computer Science from the University of Chicago under the guidance of Prof. Laszlo Babai. After doing one year of postdoc at Technion, Israel, and one year of postdoc at CWI Amsterdam, he joined Chennai Mathematical Institute in 2010. He joined the Indian Statistical Institute in 2018. His main area of interest is Theoretical Computer Science with a particular focus on query complexity, property testing, Fourier Analysis of Boolean functions, streaming algorithms, and graph algorithms. Recently he has been using property testing techniques in other more applied areas.