ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > INFROMATION COMPLEXITY:
Reports tagged with infromation complexity:
TR07-014 | 23rd January 2007
Amit Chakrabarti

Lower Bounds for Multi-Player Pointer Jumping

We consider the $k$-layer pointer jumping problem in the one-way multi-party number-on-the-forehead communication model. In this problem, the input is a layered directed graph with each vertex having outdegree $1$, shared amongst $k$ players: Player~$i$ knows all layers {\em except} the $i$th. The players must communicate, in the order $1,2,\ldots,k$, ... more >>>



ISSN 1433-8092 | Imprint