Lower Bounds for Four-player Pointer Jumping David

In four-player pointer jumping, players observe some of the edges in a directed graph con-sisting of five layers of nodes numbered 0... 4 where layer 0 has a single node and layer 4 has two nodes. All nodes except those in the last layer possess a single edge pointing to a node in the next layer. Players wish to calculate the node reached by following the path of edges from the first layer in the graph to the last. In the general input model for pointer jumping, Player i observes all edges in the graph except those leading from layer i − 1 to layer i. We give a lower bound for the one-way communication complexity of the four-player player pointer jumping function with the added restriction to the general input model that Player 3 does not see the edges from layer 1 to layer 2. As an appendix, we provide observations obtained in our investigation into four-player pointer jumping function in the general model. Acknowledgments I am grateful to my committee members, professors Prasad Jayanti and Peter Winkler.