Abstract
It is proved that the probabilistic communication complexity of the identity function in a 3-computer model isO(√n).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. Lovasz. Communication complexity: a survey. InPaths, Flows and VLSI Layout (Korte, Lovasz, Promel, Schrijver, eds.). Springer-Verlag, New York, 1990, pp. 235–266.
F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977.
Andrew C. Yao. Some complexity questions related to distributed computing.Proceedings of the 11th ACM Symposium on the Theory of Computing, 1979, pp. 209–213.
Author information
Authors and Affiliations
Additional information
Communicated by A. C.-C. Yao.
This research was supported by Latvian Science Council Grant No. 93.599.
Rights and permissions
About this article
Cite this article
Ambainis, A. Communication complexity in a 3-computer model. Algorithmica 16, 298–301 (1996). https://doi.org/10.1007/BF01955678
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01955678