Abu-Mostafa, Yaser S. (1987) On the Time-Bandwidth Proof in VLSI Complexity. IEEE Transactions on Computers, 36 (2). pp. 239-240. ISSN 0018-9340 http://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87
![[img]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 474Kb |
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87
Abstract
A subtle fallacy in the original proof [1] that the computation time T is lowerbounded by a factor inversely proportional to the minimum bisection width of a VLSI chip is pointed out. A corrected version of the proof using the idea of conditionally self-delimiting messages is given.
| Item Type: | Article |
|---|---|
| Additional Information: | © Copyright 1987 IEEE. Reprinted with permission. Manuscript received July 18, 1985; revised October 15, 1985. This work was supported by the Program in Advanced Technologies (Aerojet, GM, GTE, TRW). |
| Subject Keywords: | Bisected graph, computation time, information theory, lower bounds, self-delimiting, VLSI complexity |
| Record Number: | CaltechAUTHORS:ABUieeetc87 |
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87 |
| Alternative URL: | http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=35261&arnumber=1676888&count=18&index=13 |
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. |
| ID Code: | 7011 |
| Collection: | CaltechAUTHORS |
| Deposited By: | Archive Administrator |
| Deposited On: | 05 Jan 2007 |
| Last Modified: | 26 Dec 2012 09:27 |
Repository Staff Only: item control page
