**On the Role of Shared Entanglement** - Dmitry Gavinsky

Despite the apparent similarity between shared randomness and
shared entanglement in the context of Communication Complexity, our
understanding of the latter is not as good as of the former.
In particular, there is no known " entanglement analogue" for the
famous theorem by Newman, saying that the number of shared random
bits required for solving any communication problem can be at most
logarithmic in the input length (i.e., using more than O(log(n))
shared random bits would not reduce the complexity of an optimal
solution).
We prove that the same is not true for entanglement.
We establish a wide range of tight (up to logarithmic factors)
entanglement vs. communication trade-offs for relational problems.
We show that relatively small increase in the number of available
qubits of entanglement can lead to much more efficient solution, the
gain is exponential in some cases.