TY - GEN

T1 - A model of computation for VLSI with related complexity results

AU - Chazelle, Bernard

AU - Monier, Louis

PY - 1981/5/11

Y1 - 1981/5/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84976862424&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976862424&partnerID=8YFLogxK

U2 - 10.1145/800076.802485

DO - 10.1145/800076.802485

M3 - Conference contribution

AN - SCOPUS:84976862424

SN - 0897910419

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 318

EP - 325

BT - Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981

PB - Association for Computing Machinery

T2 - 13th Annual ACM Symposium on Theory of Computing, STOC 1981

Y2 - 11 June 1981 through 13 June 1981

ER -