Complexity seminar

Quantum versus classical simultaneity in communication complexity

We will see a bipartite partial function, which has no efficient solution in the model of randomised simultaneous
message passing (with shared randomness), but has an efficient protocol in the model of quantum simultaneous message
passing – even without shared randomness.

This can be interpreted as the strongest known − as of today − example of "super-classical" capabilities of the
weakest studied model of quantum communication.