Seminar: October 6, 2008

Toniann Pitassi, University of Toronto

Separating the analogs of NP, BPP and P in the NOF Multiparty Communication Model

Number-on-forehead communication protocols are a fascinating model of computation where k collaborating players are trying to evaluate a function, f, where the input to the function is partitioned into k pieces, where the i-th piece, $x_i$, is placed on player $i$'s forehead. Thus each player sees all but his/her own input. In order to compute $f$, the players communicate by writing bits on a shared blackboard and the complexity of the protocol is the number of bits that are communicated. This model is very important has found applications in a surprising variety of areas, including circuit complexity, pseudorandomness, and proof complexity.

In this model, a protocols is said to be efficient if it has complexity polylogn. Correspondingly, $P^{cc}_k$, $BPP^{cc}_k$, and $NP^{cc}_k$ are the NOF communication complexity analogs of the standard complexity classes. For example, $RP^{cc}_k$ is the class of functions having efficient one-sided-error communication complexity, and one of the most fundamental open problems is to separate these classes.

In this talk we will discuss two new results. Our first result (joint with Paul Beame, Matei David and Philipp Woelfel), gives a function that has an efficient randomized protocol, but requires linear complexity in the deterministic model, for up to $k=n^{\epsilon}$ players. Thus we separate $BPP^{cc}_k$ from $P^{cc}_k$. In our second theorem (joint with Matei David and Emanuele Viola), we exhibit an explicit function that can be computed by a nondeterministic NOF protocol communicating $O(logn)$ bits but requiring nearly linear number of bits of communication for randomized NOF protocols with $k=\delta \log n$ players for any fixed $\delta <1$. Thus, we separate $NP^{cc}_k$ from $RP^{cc}_k$. The first proof is unusual in that it is nonconstructive; for the second proof, we simplify and extend ideas from several recent breakthrough papers (Sherstov, Lee-Shraibman, and Chattopadhyay-Ada). Finally we will discuss recent extensions of our second result (Beame and Huynh-Ngoc), and applications of these results in proof complexity.