Resources for Quantum Communication Complexity

Question

I recently came to know about this interesting topic of "communication complexity". In simple words, Wikipedia defines it as:

In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. It was introduced by Andrew Yao in 1979, who investigated the following problem involving two separated parties, traditionally called Alice and Bob. Alice receives an n-bit string $x$ and Bob another $n$-bit string $y$, and the goal is for one of them (say Bob) to compute a certain function $f(x,y)$ with the least amount of communication between them. Of course, they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function $f$, but the idea here is to find clever ways of calculating $f$ with fewer than n bits of communication. Note that in communication complexity, we are not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used.

Now, I was going through the first couple of pages of this paper: "Quantum Communication Complexity (A Survey) - Brassard". Apparently, it seems that if the non-communicating parties are previously entangled then more bits of information may be communicated than in the classical case. The paper looks nice, and so I'll read further. However, are there any other important papers or texts which are "must-reads" when learning about "quantum communication complexity"? (I'm mostly interested in the theoretical/algorithmic side)

Answer 1

For a review of the subject, see this paper: "Non-locality and Communication Complexity" https://arxiv.org/abs/0907.3584

Answer 2

One recent breakthrough which is not covered in that survey is cheat sheets. See,

Separations in communication complexity using cheat sheets and information complexity; Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha; arXiv:1605.01142 [quant-ph]

It might be a good idea to first familiarize yourself with the cheat sheet framework.

Separations in query complexity using cheat sheets; Scott Aaronson, Shalev Ben-David, Robin Kothari; arXiv:1511.01937 [quant-ph]

Personally, I like thinking about query complexity as a whole instead of specializing in communication complexity. A lot of theorems in traditional query complexity can be lifted into communication complexity, and indeed that is what they do in the above paper.