TY - GEN

T1 - Lower bounds for VLSI

AU - Lipton, Richard J.

AU - Sedgewick, Robert

N1 - Funding Information:
t Supporled in part b.~ NSF #170C938 't f Suppor|c:d in part by NSF
Publisher Copyright:
© 1981 ACM.

PY - 1981/5/11

Y1 - 1981/5/11

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

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

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

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

U2 - 10.1145/800076.802482

DO - 10.1145/800076.802482

M3 - Conference contribution

AN - SCOPUS:85034843873

SN - 0897910419

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

SP - 300

EP - 307

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 -