CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:ABUieeetc87

[img]
Preview
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