We prove that the set disjointness problem has randomized communication complexity
\Omega(\sqrt{n}/2^{k}k) in the number-on-the-forehead model with k parties, a quadratic improvement
on the previous bound \Omega(\sqrt{n}/2^{k})^{1/2}. Our result remains valid for quantum
protocols, where it is essentially tight. Proving it was an open problem since 1997, ... more >>>