scientific article; zbMATH DE number 4051518
This paper is the first part of the work having the following three aims: 1. To introduce new frameworks useful for the study of computational properties of VLSI circuits. 2. To present some new and basic results concerning the ideas from 1. 3. To formulate a large number of open problems and research directions for further research in this area. This Part I is devoted to the mathematical formalization of the notion of a VLSI circuit [\textit{C. D. Thompson}: A complexity theory for VLSI, Doctoral Diss., CMU-CS-80-140, Comput. Sci. Dep., Carnagie-Mellon Univ., Pittsburg (1980)], and the technique for proving lower bounds on the area-time squared complexity measure is presented [\textit{A. V. Aho}, \textit{J. D. Ullman} and \textit{M. Yanakakis}: On notions of information transfer in VLSI circuits, In: Proc. 15th ACM Symp. Theory of Computing, 133-139 (1983); \textit{J. D. Ullman}: Computational aspects of VLSI (1984; Zbl 0539.68021)]. New results are obtained in the comparison of the computational power of different types of circuits.
- scientific article; zbMATH DE number 4061153
- scientific article; zbMATH DE number 4108150
- scientific article; zbMATH DE number 4078802
- scientific article; zbMATH DE number 4102489
- scientific article; zbMATH DE number 3905849
- A model of computation for VLSI with related complexity results
- scientific article; zbMATH DE number 3990864
- The advantages of a new approach to defining the communication complexity for VLSI
- The advantages of a new approach to defining the communication complexity for VLSI
- On the VLSI complexity of some arithmetic and numerical problems
- On problem transformability in VLSI
- On the VLSI complexity of some arithmetic and numerical problems
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- Lower bounds on the area complexity of Boolean circuits
- scientific article; zbMATH DE number 4181292 (Why is no real title available?)
- scientific article; zbMATH DE number 3847304 (Why is no real title available?)
- scientific article; zbMATH DE number 4135399 (Why is no real title available?)
- scientific article; zbMATH DE number 3919826 (Why is no real title available?)
- A model of computation for VLSI with related complexity results
- The VLSI Complexity of Selected Graph Problems
- scientific article; zbMATH DE number 4043241 (Why is no real title available?)
- scientific article; zbMATH DE number 4061153 (Why is no real title available?)
- scientific article; zbMATH DE number 4078802 (Why is no real title available?)
- scientific article; zbMATH DE number 4102489 (Why is no real title available?)
- scientific article; zbMATH DE number 4108150 (Why is no real title available?)
- scientific article; zbMATH DE number 61460 (Why is no real title available?)
- scientific article; zbMATH DE number 4003486 (Why is no real title available?)
- A nonlinear lower bound on the practical combinational complexity
- A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
- A nonlinear lower bound on the practical combinational complexity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787930)