Multiparty Communication Complexity of Disjointness

Understand

We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant.

• For k=o(loglog n), the bounds remain super-polylogarithmic i.e.
• (log n)^omega(1).
• The previous best lower bound for three players until recently was Omega(log n).