One-way multiparty communication lower bound for pointer jumping with applications (Q532058)

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 \(\Omega (n^{1/(k-1)})\) bits must be sent and the bounds remain nontrivial up to \(k=(\log n)^{1/2-\epsilon}\) for any \(\epsilon > 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 \(\Omega (n^{\Omega (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.