A Caltech Library Service

On the Time-Bandwidth Proof in VLSI Complexity

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.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
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).
Funding AgencyGrant Number
Caltech Program in Advanced TechnologiesUNSPECIFIED
Subject Keywords:Bisected graph, computation time, information theory, lower bounds, self-delimiting, VLSI complexity
Issue or Number:2
Record Number:CaltechAUTHORS:ABUieeetc87
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7011
Deposited By: Archive Administrator
Deposited On:05 Jan 2007
Last Modified:08 Nov 2021 20:38

Repository Staff Only: item control page