Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multi-party communication:
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 >>>

TR13-044 | 25th March 2013
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

Shared Randomness and Quantum Communication in the Multi-Party Model

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

ISSN 1433-8092 | Imprint