| 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.