Lower bounds for VLSI

Richard J. Lipton, Robert Sedgewick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

85 Scopus citations

Abstract

Increased use of Very Large Scale Integration (VLSI) for the fabrication of digital circuits has led to increased interest in complexity results on the inherent VLSI difficulty of various problems. Lower bounds have been obtained for problems such as integer multiplication (1,2), matrix multiplication [7], sorting [8], and discrete Fourier transform [9], all within VLSI models similar to one originally developed by Thompson [8.9]. The lower bound results all pertain to a space-time trade-off measure that arises naturally within this model. In particular, for all the problems listed above, the results show that if A is the area used by a VLSI circuit to compute one of the n-input, n-output functions listed above, and T is the time required for the computation, then the bound.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
PublisherAssociation for Computing Machinery
Pages300-307
Number of pages8
ISBN (Print)0897910419
DOIs
StatePublished - May 11 1981
Externally publishedYes
Event13th Annual ACM Symposium on Theory of Computing, STOC 1981 - Milwaukee, United States
Duration: Jun 11 1981Jun 13 1981

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other13th Annual ACM Symposium on Theory of Computing, STOC 1981
CountryUnited States
CityMilwaukee
Period6/11/816/13/81

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Lower bounds for VLSI'. Together they form a unique fingerprint.

  • Cite this

    Lipton, R. J., & Sedgewick, R. (1981). Lower bounds for VLSI. In Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981 (pp. 300-307). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800076.802482