A model of computation for VLSI with related complexity results

Bernard Chazelle, Louis Monier

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

30 Scopus citations

Abstract

We propose a new model of compulation for VLSI which is a refinement of previous models and makes the additional assumption that the lime for propagating information is linear in the distance. Our approach is motivated by the failure of previous models to allow for realistic asymptotic analysis. While accommodating for basic laws of physics, this model tries to be most general and technology-independent. Thus, from a complexity viewpoint, it is especially suited for deriving lower bounds and trade-offs. We present new results for a number of problems including fan-in, addition, transitive functions, matrix multiplication, and sorting.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
PublisherAssociation for Computing Machinery
Pages318-325
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 'A model of computation for VLSI with related complexity results'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Monier, L. (1981). A model of computation for VLSI with related complexity results. In Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981 (pp. 318-325). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800076.802485