Theory of Computing
-------------------
Title     : Separating Deterministic from Randomized Multiparty Communication Complexity
Authors   : Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel
Volume    : 6
Number    : 9
Pages     : 201-225
URL       : https://theoryofcomputing.org/articles/v006a009

Abstract
--------

  We solve some fundamental problems in the number-on-forehead (NOF) 
  k-player communication model.    We show that there exists a function 
  which has at most logarithmic communication complexity for randomized 
  protocols with one-sided false-positives error probability of 1/3,
  but which has linear communication complexity for deterministic 
  protocols, and in fact, even for the more powerful nondeterministic 
  protocols.   The result holds for every  epsilon > 0  and every 
  k \le 2^{(1-epsilon)n}  players, where  n  is the number of 
  bits on each player's forehead.    As a consequence, we obtain the 
  NOF communication class separation  coRP \not\subset NP.  This in
  particular implies that  P \neq RP  and  NP \neq coNP.
  We also show that for every  epsilon > 0  and every  k \le n^{1-epsilon},
  there exists a function which has constant randomized complexity for 
  public coin protocols but at least logarithmic complexity for private 
  coin protocols.   No larger gap between private and public coin protocols 
  is possible.

  Our lower bounds are existential; no explicit function is known to
  satisfy nontrivial lower bounds for  k \ge log n  players.
  However, for every  epsilon > 0  and every  k \le (1-epsilon) log n
  players, the   NP \neq  coNP  separation (and even the  
  coNP \not\subset MA  separation) was obtained independently by 
  Gavinsky and Sherstov (2010) using an explicit construction.
  In this work, for  k  < (1/9) log n  players, we exhibit an 
  explicit function which has communication complexity  O(1)  
  for public coin protocols and  Omega(log n)  for deterministic 
  protocols.  This improves the best previously known deterministic 
  lower bound for a function with efficient randomized protocols, 
  which was  Omega(log log n)  (Beigel, Gasarch, Glenn, 2006).

  It follows from our existential result that any function that is complete 
  for the class of functions with polylogarithmic nondeterministic  k-player
  communication complexity does not have polylogarithmic deterministic 
  complexity.   We show that the set intersection function, which is 
  complete in the number-in-hand model, is not complete in the NOF model 
  under cylindrical reductions.