{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T22:29:47Z","timestamp":1673476187632},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1984,12,1]],"date-time":"1984-12-01T00:00:00Z","timestamp":470707200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1984,12]]},"DOI":"10.1007\/bf01744433","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T01:31:02Z","timestamp":1118885462000},"page":"47-70","source":"Crossref","is-referenced-by-count":95,"title":["New lower bound techniques for VLSI"],"prefix":"10.1007","volume":"17","author":[{"given":"Frank Thomson","family":"Leighton","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01744433_CR1","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/978-3-642-68402-9_12","volume-title":"Proceedings of the CMU Conference on VLSI Systems and Computations","author":"G. M. Baudet","year":"1981","unstructured":"G. M. Baudet, On the area required by VLSI circuits,Proceedings of the CMU Conference on VLSI Systems and Computations, Edited by H. T. Kung, B. Sproull and G. Steele, Computer Science Press, Rockville, Maryland, October 1981, pp. 100\u2013107."},{"key":"BF01744433_CR2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/0020-0190(80)90034-4","volume":"11","author":"R. P. Brent","year":"1980","unstructured":"R. P. Brent and H. T. Kung, On the area of binary tree layouts,Information Processing Letters, No. 11, 1980, pp. 44\u201346.","journal-title":"Information Processing Letters"},{"key":"BF01744433_CR3","unstructured":"S. N. Bhatt and C. E. Leiserson, Minimizing the longest edge in a VLSI layout, unpublished manuscript, MIT Lab for Computer Science, 1981."},{"key":"BF01744433_CR4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/978-3-642-68402-9_10","volume-title":"Proceedings of the CMU Conference on VLSI Systems and Computations","author":"G. Bilardi","year":"1981","unstructured":"G. Bilardi, M. Pracchi and F. P. Preparata, A critique and appraisal of VLSI models of computation,Proceedings of the CMU Conference on VLSI Systems and Computations, Edited by H. T. Kung, B. Sproull and G. Steele, Computer Science Press, Rockville, Maryland, October 1981, pp. 81\u201388."},{"key":"BF01744433_CR5","doi-asserted-by":"crossref","unstructured":"B. Chazelle and L. Monier, A model of computation for VLSI with related complexity results,Proceedings of the 13th Annual ACM Symposium on Theory of Computation, May 1981, pp. 318\u2013325.","DOI":"10.1145\/800076.802485"},{"key":"BF01744433_CR6","unstructured":"P. R. Cappello and K. Steiglitz, Area-efficient VLSI structures for multiplying at clock rate, Technical Report # 289, Department of EECS, Princeton University, September 1981."},{"key":"BF01744433_CR7","unstructured":"D. Gannon, personal communication, November 1981."},{"key":"BF01744433_CR8","unstructured":"H. Jai-Wei and A. L. Rosenberg, Graphs that are similar to binary trees,Proceedings of the 13th Annual ACM Symposium on Theory of Computation, May 1981, pp. 334\u2013341."},{"key":"BF01744433_CR9","doi-asserted-by":"crossref","unstructured":"D. J. Kleitman, The crossing number ofK 5,n ,Journal of Combinatorial Theory, 9, 4, December 1970, pp. 315\u2013323.","DOI":"10.1016\/S0021-9800(70)80087-4"},{"key":"BF01744433_CR10","doi-asserted-by":"crossref","unstructured":"D. Kleitman, F. T. Leighton, M. Lepley and G. L. Miller, New layouts for the shuffle-exchange graph,Proceedings of the 13th ACM Symposium on Theory of Computing, May 1981, pp. 278\u2013292.","DOI":"10.1145\/800076.802480"},{"key":"BF01744433_CR11","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson, Area-efficient graph layouts (for VLSI),Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, October 1980, pp. 270\u2013281.","DOI":"10.1109\/SFCS.1980.13"},{"key":"BF01744433_CR12","unstructured":"C. E. Leiserson,Area Efficient VLSI Computation, Ph.D. dissertation, Department of Computer Science, Carnegie-Mellon University, 1980."},{"key":"BF01744433_CR13","doi-asserted-by":"crossref","unstructured":"F. T. Leighton,Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI, Ph.D. dissertation, Mathematics Department, Massachusetts Institute of Technology, August 1981.","DOI":"10.1109\/SFCS.1981.22"},{"key":"BF01744433_CR14","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, New lower bound techniques for VLSI,Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, October 1981, pp. 1\u201312.","DOI":"10.1109\/SFCS.1981.22"},{"key":"BF01744433_CR15","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, A layout strategy for VLSI which is provably good,Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 1982, pp. 85\u201398.","DOI":"10.1145\/800070.802180"},{"key":"BF01744433_CR16","first-page":"289","volume-title":"Proceedings of the VLSI 81 Conference","author":"F. T. Leighton","year":"1981","unstructured":"F. T. Leighton and G. L. Miller, Optimal layouts for small shuffle-exchange graphs,Proceedings of the VLSI 81 Conference, Edited by J. P. Gray, Academic Press, London, August 1981, pp. 289\u2013299."},{"key":"BF01744433_CR17","unstructured":"F. T. Leighton and A. L. Rosenberg, Three-dimensional circuit layouts, unpublished manuscript, 1982."},{"key":"BF01744433_CR18","doi-asserted-by":"crossref","unstructured":"R. J. Lipton and R. Sedgewick, Lower bounds for VLSI,Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 1981, pp. 300\u2013307.","DOI":"10.1145\/800076.802482"},{"key":"BF01744433_CR19","doi-asserted-by":"crossref","unstructured":"R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem,SIAM Journal of Computing, 0, 3, August 1980, pp. 615\u2013627.","DOI":"10.1137\/0209046"},{"key":"BF01744433_CR20","unstructured":"C. Mead and L. Conway,Introduction to VLSI Systems, Addison-Wesley Publishing Company, Reading, Massachusetts, October 1980."},{"key":"BF01744433_CR21","doi-asserted-by":"crossref","unstructured":"D. E. Muller and F. P. Preparata, Bounds to complexities of networks for sorting and for switching,Journal of the ACM, 22, 2, April 1975, pp. 195\u2013201.","DOI":"10.1145\/321879.321882"},{"key":"BF01744433_CR22","unstructured":"D. Nath, S. N. Maheshwari and P. C. P. Bhatt, Efficient VLSI networks for parallel processing based on orthogonal trees, unpublished manuscript, 1981."},{"key":"BF01744433_CR23","doi-asserted-by":"crossref","unstructured":"M. S. Patterson, W. L. Ruzzo and L. Snyder, Bounds on minimax edge length for complete binary trees,Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 1981, pp. 293\u2013299.","DOI":"10.1145\/800076.802481"},{"key":"BF01744433_CR24","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and J. E. Vuillemin, The cube-connected-cycles: a versatile network for parallel computation,Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, October 1979, pp. 140\u2013147.","DOI":"10.1109\/SFCS.1979.43"},{"issue":"2","key":"BF01744433_CR25","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(80)90006-X","volume":"11","author":"F. P. Preparata","year":"1980","unstructured":"F. P. Preparata and J. E. Vuillemin, Area-time optimal VLSI networks for multiplying matrices,Info. Proc. Letters, 11, 2, Oct. 20, 1980, pp. 77\u201380.","journal-title":"Info. Proc. Letters"},{"key":"BF01744433_CR26","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-642-68402-9_14","volume-title":"Proceedings of the CMU Conference on VLSI Systems and Computations","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo and L. Snyder, Minimum edge length planar embeddings of trees,Proceedings of the CMU Conference on VLSI Systems and Computations, Edited by H. T. Kung, B. Sproull and G. Steele, Computer Science Press, Rockville, Maryland, October 1981, pp. 119\u2013123."},{"key":"BF01744433_CR27","unstructured":"J. E. Savage, Area-time tradeoffs for matrix multiplication and related problems in VLSI models,Proceedings of the 17th Annual Allerton Conference on Communications, Control and Computing, October 1979, pp. 670\u2013676."},{"key":"BF01744433_CR28","doi-asserted-by":"crossref","unstructured":"C. D. Thompson, Area-time complexity for VLSI,Proceedings of the 11th Annual ACM Symposium on Theory of Computing, May 1979, pp. 81\u201388.","DOI":"10.1145\/800135.804401"},{"key":"BF01744433_CR29","unstructured":"C. D. Thompson,A Complexity Theory for VLSI, Ph.D. dissertation, Department of Computer Science, Carnegie-Mellon University, 1980."},{"key":"BF01744433_CR30","doi-asserted-by":"crossref","unstructured":"C. D. Thompson, The VLSI complexity of sorting,IEEE Transactions on Computers, Vol. C-32, 12, December 1983, pp. 1171\u201384.","DOI":"10.1109\/TC.1983.1676178"},{"key":"BF01744433_CR31","doi-asserted-by":"crossref","unstructured":"J. E. Vuillemin, A combinatorial limit to the computing power of VLSI circuits,Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, November 1980, pp. 294\u2013300.","DOI":"10.1109\/SFCS.1980.1"},{"key":"BF01744433_CR32","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, Universality considerations in VLSI circuits,IEEE Transactions on Computers, C-30, 2, February 1981, pp. 135\u2013140.","DOI":"10.1109\/TC.1981.6312176"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744433.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01744433\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:20:21Z","timestamp":1586287221000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01744433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,12]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,12]]}},"alternative-id":["BF01744433"],"URL":"http:\/\/dx.doi.org\/10.1007\/bf01744433","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":["Computational Theory and Mathematics","General Mathematics","Theoretical Computer Science","Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[1984,12]]}}}