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
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87
A subtle fallacy in the original proof  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.
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||05 Jan 2007|
|Last Modified:||26 Dec 2012 09:27|
Repository Staff Only: item control page