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. doi:10.1109/TC.1987.1676888. https://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 485kB |
Use this Persistent URL to link to this item: https://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 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||
| Additional Information: | © 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). | ||||||||||||
| Funders: |
| ||||||||||||
| Subject Keywords: | Bisected graph, computation time, information theory, lower bounds, self-delimiting, VLSI complexity | ||||||||||||
| Issue or Number: | 2 | ||||||||||||
| DOI: | 10.1109/TC.1987.1676888 | ||||||||||||
| Record Number: | CaltechAUTHORS:ABUieeetc87 | ||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87 | ||||||||||||
| 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: | 08 Nov 2021 20:38 |
Repository Staff Only: item control page
