Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness
Anup Rao, Amir Yehudayoff · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.