Abstract.
We present several results regarding randomized one-round communication complexity. Our results include a connection to the VC-dimension, a study of the problem of computing the inner product of two real valued vectors, and a relation between “simultaneous” protocols and one-round protocols.
Article PDF
Similar content being viewed by others
Use our pre-submission checklist
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: May 2, 1996.
Rights and permissions
About this article
Cite this article
Kremer, I., Nisan, N. & Ron, D. On Randomized One-round Communication Complexity. Comput. complex. 8, 21–49 (1999). https://doi.org/10.1007/s000370050018
Issue Date:
DOI: https://doi.org/10.1007/s000370050018