The advantages of a new approach to defining the communication complexity for VLSI (Q5966473)
From MaRDI portal
scientific article; zbMATH DE number 4062585
Language | Label | Description | Also known as |
---|---|---|---|
English | The advantages of a new approach to defining the communication complexity for VLSI |
scientific article; zbMATH DE number 4062585 |
Statements
The advantages of a new approach to defining the communication complexity for VLSI (English)
0 references
1988
0 references
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.
0 references
Boolean function
0 references
languages
0 references
VLSI computations
0 references
communication complexity
0 references
VLSI circuits
0 references