Communication complexity

ABSTRACT

In this paper we prove several results concerning this complexity measure. First we establish (in a non-constructive manner) that there exist languages which cannot be recognized with less than n communication (obviously, communication n is always enough for recognizing any language). In fact, we show that for any functionf(n)-&-lt; n, there are languages recognizable with communicationf(n) but not with communicationf (n)-&-minus;1. In other words, this complexity measure possesses a very dense hierarchy or complexity classes, as miniscule increments in communication add to the languages that can be recognized.

REFERENCES

• 1: Abelson, "Lower bounds on information transfer in distributed computations," Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978.
• 2: Richard J. Lipton , Robert Sedgewick, Lower bounds for VLSI, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.300-307, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802482]
• 3: Savage, "Area-time tradeoffs for matrix multiplication and related problems in VLSI models," Proceedings of the Allerton Conference, 1979.
• 4: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 5: Vuillemin, "A combinatorial limit on the computational power of VLSI circuits," Proceedings of the 21st Annual Conference on Foundations of Computer Science, 1980, 294-300.
• 6: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• 7: Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]