COMPUTER SCIENCE/DISCRETE MATH II | |

Topic: | One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications |

Speaker: | Emanuele Viola |

Affiliation: | Harvard University and Member, School of Mathematics |

Date: | Tuesday, May 1 |

Time/Room: | 10:30am - 12:30pm/S-101 |

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.