Communication Complexity of the Multiparty Pointer Jumping Problem

Communication Complexity of the Multiparty Pointer Jumping Problem

Mario Sanchez and Joshua Brody

In standard computer science theory, one often focuses on problems where a computer has data and wants to use this data to compute an answer to a question. However, this does not encompass all of the interesting problems that occur. Consider the following situation: There are two or more agents attempting to solve a problem together. The catch is that each agent has data that is disjoint from the rest, and must then communicate their information to each other. The trivial solution would be for each agent to communicate all of their information to each other, and then solve the problem as usual; however, in problems with a large amount of data, the runtime for this protocol is very large. The field of communication complexity focuses on finding efficient protocols for solving various of these problems.

In this poster, we focus on the Multiparty Pointer Jumping Problem. We take the previous bound found by Brody et al [1] and improve it to

CC(MPJ) = O((n log n)/(log log n)).

While constructing the protocol, we also extend the Erdös-Renyi random graph model to include dependence. We believe this extension to be of independent interest in mathematics.

[1] J Brody, A Chakrabarti. Sublinear Communication Protocols for 
Multi-Party Pointer Jumping and a Related Lower Bound. 2008.