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.

Communication complexity of computing functions using unrestricted communication and one-round communication are compared. In the standard unrestricted communication each party could potentially communicate several times while in one-round communication each party is restricted to communicate at most once. Results on the ratio of these two complexities are provided for symmetric and asymmetric functions under different scenarios. These results are suitably illustrated with examples.

We consider a power-efficient communication model for wireless sensor networks where silence is used to convey information. We study the average-case and worst-case complexities of symmetric functions under this model and describe protocols that achieve them. For binary-input functions, we determine the average complexity. For ternary-input functions, we consider a special type of protocols and provide close lower and upper bounds for their worst-case complexity. We also describe the protocol that achieves the average complexity

Recent work has considered encoding a string by separately conveying its symbols and its pattern-the order in which the symbols appear. It was shown that the patterns of independent and identically distributed (i.i.d.) strings can be losslessly compressed with diminishing per-symbol redundancy. In this correspondence, the pattern redundancy of distributions with memory is considered. Close lower and upper bounds are established on the pattern redundancy of strings generated by Hidden Markov models (HMMs) with a small number of states, showing in particular that their per-symbol pattern redundancy diminishes with increasing string length. The upper bounds are obtained by analyzing the growth rate of the number of multidimensional integer partitions, and the lower bounds, using Hayman's theorem

In this paper the pattern redundancy of strings generated by hidden Markov models is bounded over unknown, possibly infinite alphabets, showing in particular that it diminishes to zero when the number of states is sufficiently small.