Silence-based communication
Lists
Only you see this
Abstract
Communication complexity - the minimum amount of communication required - for 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 nonbinary 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 multiple-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.
BibTeX
@article{dhulipala2010silence,
author = {Anand K. Dhulipala and Christina Fragouli and Alon Orlitsky},
title = {{Silence-based communication}},
journal = {IEEE Trans. Information Theory},
year = {2010},
url = {https://openreview.net/forum?id=HNvOk2bZ6yv},
}Loading related content...