Communication complexity---the minimum amount of communication required---of computing a function of data held by several parties is studied. A communication model where silence is used to convey information is introduced. For this model the worst-case and average-case complexities of symmetric functions are studied. For binary-input functions the average- and worst-case complexities are determined and the protocols achieving them are described. For functions of non-binary inputs one-round communication, where each party is restricted to communicate in consecutive stages, is considered and the extra amount of communication required by one- over multi-round communication is analyzed. For the special case of ternary-input functions close lower and upper bounds on the worst-case one-round complexity are provided and protocols achieving them are described. Protocols achieving the average-case one-round complexity for ternary-input functions are also described. These protocols can be generalized to inputs of arbitrary size.
Colin Neil Jones, Yuning Jiang, Yingzhao Lian, Xinliang Dai
Dario Floreano, Laurent Keller
Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira, Vincent Gramoli, Seth Gilbert