Disjointness is hard in the multi-party number on the forehead model

Troy Lee, Adi Shraibman

We show that disjointness requires randomized communication Omega(n^{1/(k+1)}/2^{2^k}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bo…