{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:18Z","timestamp":1787340558367,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>This paper presents initial results on the problem of allocation of the available VLSI chip\u2019s area among various functional components such as I\/Q pads, memory cells, and internal wiring. First, a general lower bound for any chip computing a transitive function is derived; this bound is tight for certain functions. The arguments used in the various derivations are later used to specify which of the components are critical depending on the relative sizes of the chip and the number of variables of the function to be computed. The general lower bound is powerful enough that many of the previously proved lower bounds (which could account only for some of the functional requirements) are obtained as explicit special cases of the new result.<\/jats:p>","DOI":"10.1137\/0214053","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"730-743","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Allocation of Area for Single-Chip Computations"],"prefix":"10.1137","volume":"14","author":[{"given":"Zvi M.","family":"Kedem","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","volume-title":"What Can Be Automated? The Computer Science and Engineering Research Study (COSERS)","author":"Arden B. W.","year":"1980"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322269"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Chazelle, L. Monier,  A model of computation for VLSI with related complexity results,  Proc. 13th Annual ACM Symposium on Theory of Computing,  1981,  318\u2013325, May","DOI":"10.1145\/800076.802485"},{"key":"R4","unstructured":"D. Yu. Grigoryev,  An application of separability and independence notions for proving lower bounds on circuit complexity,  Notes of Scientific Seminars, Vol. 60, Steklov Math. Inst.,  1976,  35\u201348, (In Russian)"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, A. Zorat,  On relations between input and communication-computation in VLSI,  Proc. 22nd Annual Symposium on Foundations of Computer Science,  1981,  37\u201344, October","DOI":"10.1109\/SFCS.1981.26"},{"key":"R6","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68402-9_11"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson,  Area-efficient graph layouts (for VLSI),  Proc. 21st Annual Symposium on Foundations of Computer Science,  1980,  270\u2013281, October","DOI":"10.1109\/SFCS.1980.13"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. J. Lipton, R. Sedgewick,  Lower bounds for VLSI,  Proc. 13th Annual ACM Symposium on Theory of Computing,  1981,  300\u2013307, May","DOI":"10.1145\/800076.802482"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. L. Rosenberg,  H. T. Kung, B.  Sproull, G.  Steele,  Three-dimensional integrated circuitry,  VLSI Systems and Computations, Computer Science Press,  1981,  69\u201380","DOI":"10.1007\/978-3-642-68402-9_9"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68402-9_8"},{"key":"R12","unstructured":"J. E. Savage,  Bounds on the performance of multilective VLSI algorithms, Rep., CS-82-10, Dept. Computer Science, Brown Univ., Providence, RI,  1982, March, pp. 1\u201328"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804401"},{"key":"R14","unstructured":"L. Valiant, Unpublished, brought to the author's attention by J. Savage"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676221"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Yao,  The entropic limitations on VLSI computations,  Proc. 13th Annual ACM Symposium on Theory of Computing,  1981,  308\u2013311, May","DOI":"10.1145\/800076.802483"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:18Z","timestamp":1787337558000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214053"],"URL":"https:\/\/doi.org\/10.1137\/0214053","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}