Title :
On the Time-Bandwidth Proof in VLSI Complexity
Author :
Abu-Mostafa, Yaser S.
Author_Institution :
Departments of Electrical Engineering and Computer Science, California Institute of Technology
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.
Keywords :
Bisected graph; VLSI complexity; computation time; information theory; lower bounds; self-delimiting; Application software; Periodic structures; Steiner trees; US Department of Transportation; Very large scale integration; Bisected graph; VLSI complexity; computation time; information theory; lower bounds; self-delimiting;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1987.1676888
