On the Time-Bandwidth Proof in VLSI Complexity
Abu-Mostafa · IEEE Transactions on Computers · 1987
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.