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.

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
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:
Alternative 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:26 Dec 2012 09:27

Repository Staff Only: item control page