The paper studies communication complexity in the “number on the forehead model”. In other words, we have $k$ players and $k$ $n$-bit inputs $(x_i)_{i=1}^k$ and the $i$-th player knows all inputs except $x_i$. The goal of the players is to compute a function on their combined inputs. The paper studies a particular variant of this model where each player only speaks once and the order in which the players speak is fixed in advance, thus we can assume that player $i$ speaks at time $i$. The main function considered is a $k$ level pointer jumping (which is essentially a $k$-fold composition of functions), where $x_i$ give the pointers on level $i$ (description of the $i$-th function). The lower bound obtained, which is tight for any constant $k$ and randomized protocols, is that $Ω(n^{1/(k-1)})$ bits must be sent and the bounds remain nontrivial up to $k=(\log n)^{1/2-ϵ}$ for any $ϵ> 0$. It is not difficult to see that the problem is easy (can be done with communication $O(\log n)$) if the players are allowed to speak in any other order. As corollaries lower bounds for related functions follow in similar models. In particular, for any constants $k$ and $r$ there is a function that requires $Ω(n^{Ω(1)})$ communication by an $r$-round $k$-party protocol but can be computed by $O(\log n)$ communication in $r’$ rounds when $r’(k-1) \geq rk$. The function can also be computed by a nondeterministic $2$-round protocol with $O(\log n)$ communication.
Reviewer: Johan Hastad (Stockholm)