The advantages of a new approach to defining the communication complexity for VLSI (Q1106661)

Communication complexity is a complexity measure which is useful for proving lower bounds on area complexity and area-time squared complexity of VLSI computations. In this paper a formal definition of S- communication complexity based on the idea of \textit{A. V. Aho}, \textit{J. D. Ullman} and \textit{M. Yannakakis} [On notions of information transfer in VLSI circuits. In: Proc. 14th Ann. ACM Symp. Theory Comput. 133-139 (1983)] is given, and its properties are compared with the original communication complexity defined by \textit{Ch. H. Papadimitriou} and \textit{M. Sipser} [J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064)]. The basic advantages of S-communication complexity presented here are the following two: (1) S-communication complexity provides the strongest lower bound \(\Omega (n^ 2)\) on \(AT^ 2\) complexity of VLSI circuits in most cases in which the communication complexity grants only smaller (for example, constant) lower bounds. (2) Proving lower bounds for S-communication complexity is technically not so hard as obtaining lower bounds for communication complexity. Further, some basic results including the properties of S-communication complexity considered as an abstract complexity measure are established.