## Dmitry Gavinsky

*Quantum Communication Cannot Simulate a Public Coin* We study the simultaneous message passing model of communication
complexity.
Building on the quantum fingerprinting protocol of Buhrman et al., Yao
recently showed that a large class of efficient classical public-coin
protocols can be turned into efficient quantum protocols without public
coin. This raises the question whether this can be done always, i.e.,
whether quantum communication can always replace a public coin in the SMP
model. We answer this question in the negative, exhibiting a communication
problem where classical communication with public coin is exponentially more
efficient than quantum communication. Together with a separation in the
other direction due to Bar-Yossef et al., this shows that the quantum SMP
model is incomparable with the classical public-coin SMP model.
In addition we give a characterization of the power of quantum
fingerprinting by means of a connection to geometrical tools from machine
learning, a quadratic improvement of Yao's simulation, and a nearly tight
analysis of the Hamming distance problem from Yao's paper.