This paper compares the communication complexity of discrete functions under different modes of computation, unifying and extending several known models. Protocols can be deterministic, nondeterministic, or probabilistic. Furthermore, in the last case the error probability may vary. On the other hand, communication can be one-way, two-way, or as an intermediate stage can consist of a fixed number $k > 1$ of rounds. The following main results are obtained. A square gap between deterministic and nondeterministic communication complexity is shown for a specific function, which is the maximum possible. This improves the results of K. Mehlhorn and E. M. Schmidt in [Proc. 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 330–337] and of A. V. Aho, J. D. Ullman, and M. Yannakakis in [Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 133–139]. For probabilistic one-way and two-way protocols linear lower bounds are proved for functions that satisfy certain independence conditions, extending the results of A. C. Yao in [Proc. 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 209–213], and in [Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, pp. 420–428]. Further, with more technical effort an exponential gap between deterministic k-round and probabilistic $(k - 1)$-round communication with fixed error probability is obtained. This generalizes the main result of P. Duris, Z. Galil, and G. Schnitger [Inform. and Comput., 73 (1987), pp. 1–22]. In contrast, for arbitrary error probabilities less than ${1 / 2}$ there is no difference between the complexity of one-way and two-way protocols, which extends the results of R. Paturi and J. Simon [J. Comput. System Sci., 33 (1986), pp. 106–123]. Finally, communication with fixed message length and uniform probability distributions is considered, and simulations of arbitrary protocols by such uniform distributions with little overhead are provided.

We compare the communication complexity of discrete functions under different modes of computation, unifying and extending several known models. Protocols can be deterministic, nondeterministic or probabilistic and in the last case the error probability may vary. On the other hand communication can be 1-way, 2-way or as an intermediate stage consist of a fixed number k > 1 of rounds.The following main results are obtained. A square gap between deterministic and nondeterministic communication complexity is shown for a specific function, which is the maximal possible. This improves the results of [MS 82] and [AUY 83]. For probabilistic 1- and 2-way protocols we prove linear lower bounds for functions that satisfy certain independence conditions, extending the results of [Y 79] and [Y 83]. Further, with more technical effort an exponential gap between deterministic k-round and probabilistic (k - 1)-round communication with fixed error probability is obtained. This generalizes the main result of [DGS 84]. On contrast for arbitrary error probabilities less than 1/2 there is no difference between the complexity of 1- and 2-way protocols, extending results of [PS 84]. Finally we consider communication with fixed message length and uniform probability distributions and give simulations of arbitrary protocols by such uniform ones with little overhead.