More “O” Abuse
Lower bounds on VLSI
Bob Sedgewick is a best selling author of computer science textbooks. His most famous book is entitled simply “Algorithms,” and countless undergrads have used it as their introduction to computing. He was also the first chair of the department of Computer Science at Princeton University. As chair he helped design the current building for Computer Science, in which he the builders encode a “secret” in the bricks on the outside of building that spell out the phrase P=NP? Clearly, P=NP is an important problem–what other problems are “encoded” onto the face of buildings?
In the 1980′s Bob and I worked on proving lower bounds for VLSI, we were part of a group of researchers that worked on proving similar results. Recall VLSI stands for “Very Large Scale Integration”, i.e, for silicon chips. All the results, ours and theirs, were of the same form: we all proved that their were restrictions on the size and speed of an integrated circuit chip that computed something. The results were of the form: if a chip computes , then
where is the size of the chip in area and is the time that the chip takes to do the computation. Note, the results prove a “space-time” tradeoff: either the chip has to be big or the chip has to be slow. Increasing the chip’s speed, for example making smaller, forces the chip to become bigger.
The way that these results are proved is interesting, since they use communication complexity type arguments. Today communication complexity is a major area of theory, our work were some of the first applications of this method of proof. While we did not invent the method, we were the first to introduce nondeterministic communication complexity. I always thought that it was neat, and a bit surprising, that nondeterminism played a role in proving lower bounds on chips. After all chips are real devices that are deterministic, but our proofs required nondeterminism. In any event we were the first to define this type of communication complexity, since then nondeterministic complexity has been studied heavily for it’s own sake.
What does this have to do with abuse of O-notation, you might ask? At the time chip manufactures made chips that computed the product of two bit integers, i.e. that computed multiplication. The was typically small, was common, yet the chips while fast were always quite large. Bob and I wondered if the results we proved could shed some light on this: did the chips have to be big in order to be fast, just as our results implied? So one day Bob and I started to work out the exact constant that was hidden in the proof that for multiplication,
Our hope was that while is not large, our methods would still say something non-trivial about the size and performance of actual chips. Luckily, the proofs were constructive so that getting a handle on the hidden constant was not too difficult. After a couple of hours at the blackboard we got the answer:
for a known . The trouble was when we plugged in or even , the bound on the size of the chip was a “joke”. The methods showed at best that the chips were not much bigger than the size of a single transistor. This was terrible, since we expected something much better. But we checked our calculations carefully, and there was no error. The constant was extremely small. Tiny. The bounds we and many others had worked hard to prove said nothing about real computations. Nothing. Bob and I stopped working on these bounds.
A challenge to the theory community is to check on the bounds that are used in both upper and lower bound theorems, not just those about chip size. In pure mathematics the exact constants for many results are not really important. However, in an area like computer science that is grounded in practice the bounds matter. It’s not enough to say that we can show that something is larger than for some . It makes a huge difference whether the is large, medium, small, or tiny. The difference is one that we currently ignore at best–I think this is a kind of intellectual dishonesty that we must avoid.
Finally, one could view this whole area as a potential opportunity. If we spend time and energy trying to understand the exact behavior of our results, we may just discover new methods. We may be led to methods and ideas that allow realistic constants. I certainly hope that this happens.