Computer Science/Discrete Mathematics Seminar II

In this talk we study the one-way multi-party communication model, in which each of the k parties speaks exactly once in its turn. For every fixed k, we prove a tight lower bound of Omega(n^(1/(k-1))) on the probabilistic communication complexity of pointer jumping, which is the problem of following k pointers on a k-layered tree, where the pointers of the i-th layer reside on the forehead of the i-th party to speak. The lower bound remains nontrivial even for k = (log n)^(1/3) parties. Previous to our work a lower bound was known only for k=3, and in very restricted models for k>3. Our results have the following consequences to other models and problems, extending previous work in several directions. The one-way model is strong enough to capture *general* (non one-way) multi-party protocols of bounded rounds. Thus we generalize to this multi-party model results on two directions studied in the classical 2-party model. First, we prove a round hierarchy: We give an exponential separation between the power of r and 2r rounds in general k-party protocols. Second, we prove that nondeterminism gives an exponential saving in communication for general k-party protocols with r rounds. (Here, k and r are arbitrary constants.) The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of Omega(n^(1/(k-1))) on the probabilistic communication complexity of k-set disjointness in the one-way model, which was known only for k=3 parties. This is joint work with Avi Wigderson.