Rounds in Communication Complexity Revisited

Authors:
  • NNNoam Nisan
    Noam Nisan
  • AWAvi Wigderson
    Avi Wigderson
Publisher website
Google Scholar
Abstract
The k-round two-party communication complexity was studied in the deterministic model by [P. H. Papadimitriou and M. Sipser, Proc. of the 14th STOC, 1982, pp. 330–337] and [P. Duris, Z. Galil, and G. Schnitger, Proc. of the 16th STOC, 1984, pp. 81–91] and in the probabilistic model by [A. C. Yao, Proc. of the 24th FOCS, 1983, pp. 420–428] and [B. Halstenberg and R. Reischuk, Proc. of the 20th STOC, 1988, pp. 162–172]. This paper presents new lower bounds that give (1) randomization is more powerful than determinism in k-round protocols, and (2) an explicit function which exhibits an exponential gap between its k and $(k - 1)$-round randomized complexity. This paper also studies the three-party communication model, and exhibits an exponential gap in 3-round protocols that differ in the starting player. Finally, this paper shows new connections of these questions to circuit complexity, that motivate further work in this direction.