Improved Separations between Nondeterministic and Randomized Multiparty Communication
Matei David, Toniann Pitassi, Emanuele Viola · ACM Transactions on Computation Theory · 2009
We exhibit an explicit function f : {0, 1} n →{0, 1} that can be computed by a nondeterministic number-on-forehead protocol communicating O (log n ) bits, but that requires n Ω(1) bits of communication for randomized number-on-forehead protocols with k = δ ·log n players, for any fixed δ < 1. Recent breakthrough results for the Set-Disjointness function [Lee and Shraibman 2008; Chattopadhyay and Ada 2008] based on the work of Sherstov [2009; 2008a] imply such a separation but only when the number of players is k < loglog n . We also show that for any k = A ·loglog n the above function f is computable by a small circuit whose depth is constant whenever A is a (possibly large) constant. Recent results again give such functions but only when the number of players is k < loglog n .