Silence-Based CommunicationReport as inadecuate

Silence-Based Communication - Download this document for free, or read online. Document in PDF available to download.

Published in: IEEE Transaction on Information Theory, vol. 56, num. 1 Publication date: 2010

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.

Keywords: Communication complexity ; function computation ; multiple-round ; one-round ; sensor networks ; symmetric functions ; Multiparty Protocols ; Sensor Networks ; Cost ; Complexity ; Channel ; Code Reference ARNI-ARTICLE-2009-002doi:10.1109/TIT.2009.2034813View record in Web of Science

Author: Dhulipala, Anand K.; Fragouli, Christina; Orlitsky, Alon


Related documents