Abstract: Alice, Bob and Charlie play the following communication game.
Each of them gets a subset of {1..n} written on his forehead.
This way for example Alice can see the subset on Bob's forehead as well as
Charlie's. But she cannot see the subset on her own forehead. They then
communicate between themselves, using a predefined protocol, in order
to decide whether the three subsets have a joint element or not.
How many bits of communication do Alice, Bob and Charlie need to exchange
in order to solve this problem ?
If in addition the players are allowed to flip a random coin and err
with small probability. How many bits do they need to communicate then ?

We show that the players need at least \Omega(n^{1/4}) bits of communication
to find the answer, even if random bits are used.
The previous best lower bound was $\log n$.

The proof involves showing lower bounds on some norm, defined on 3-tensors,
and its approximation variant.

Joint work with Troy Lee from Columbia University.