What is efficient?

In my previous post, I wrote about how calling P "efficient computation" is nothing more than bad philosophy. I think a lot more examples are in order.

Are problems constant size? Opinions that P is efficient often stem from the following understanding of what computers are used for. Let's say that I have to optimize the bus schedules in NYC, and there are some 200 bus routes to consider. Certainly, an O(n³) algorithm is worse than an O(n lg n) algorithm, but there is a really large gap between both of these, and an O(n!) algorithm. Indeed, with an O(n³) running time I will have to buy more/bigger computers, and let them run for a week instead of 30 seconds. But with an O(n!) algorithm, throwing more resources at the problem is simply not possible (I would need a computer the size of Earth). In general, as machines grow in power, more and more polynomial algorithms become usable, whereas exponential algorithms remain similarly useless.

The big fallacy of this argument is assuming that we know what we're doing. We don't! The problem, and the size of the problem changes, often faster that the speed of our computers.

If you give me an O(n³) algorithm for the bus scheduling problem, all of a sudden I will realize that I can ask for more. Before, I was assuming that each bus route should have a fixed frequency, but certainly I can get better results (in real life) if I allow variable gaps between consecutive buses. All of a sudden, the number of variables in your problem will explode (e.g., there might be 30 cycles on the same bus route during the day). Why did it explode? Only because you told me that you had a faster algorithm.

Twenty years ago, nobody could envision problems of the scale that Google solves today. Now we can, and it's all a fault of the hardware guys. They managed to push storage capacity (disk and RAM) so much, that it makes sense to ask questions about billions of web pages.

For as long as Moore's law is (was) active, we can at best expect the memory size and the processor "power" to grow at the same rate. Even worse, processor power will probably lag behind: doubling the density will roughly double my RAM capacity, but algorithmically I will probably not be able to do double the computation on the CPU (it's hard to exploit parallelism perfectly). With an exponential gap between memory and CPU, it's only linear time algorithms that survive.

We don't know what we're doing. A related issue, highlighted in the buses example, is that we don't know what we ultimately want to solve. It depends on what we can solve. If I give you a faster algorithm, you will want to model your problem with more details, making my algorithm too slow.

The core problem that Internet routers have to solve comes down to nothing more than a binary search (each subnetwork has an IP range, and I have to figure out in which of these ranges my destination IP lies). Could we solve it in O(lg n)? With current data rates and traffic, we probably could (barely). But if we speed it up, we can now maintain that interesting statistic, which allows us to bill customers more accurately. And if we could speed it up some more, we have time-per-packet to fit that extra component, which will allow us to track virus infections ex post facto.

Functionality is never fixed. The more you can do, the more I will ask you to do. It makes equal sense to improve an O(n!) algorithm to O(2ⁿ), or to improve an O(n³) algorithm to O(n²), or to improve hash tables by 20% (they're already constant time!). In all cases, you will notice that the problem size was just at the limit of what you could handle, and the new algorithm will make somebody very happy.

Apart from the many examples that I heard about at ATT, I can give another. I am working with an OR guy, the kind of person who teaches at Business School and spent significant time optimizing truck schedules for Amazon (not in theory, but actually chasing 2% improvements that they implemented). Do you know what problem he brought to me? He wants to improve an O(n lg n) algorithm.

I remember a quote from David Karger in Advanced Algorithms. He said that one week after you improve a running time from O(n²) to O(n lg²n), you should celebrate. But two years later, you should work on improving it to O(n); most likely, it is a very interesting problem by now.

Intellectual curiosity. Ultimately, all arguments about reality cannot compete with our (very developed) sense of the aesthetic. What lives and dies in a branch of mathematics is determined by what trigers our intellectual curiosity.

My ferm belief is that whenever you have a clean and ellegant problem, there will some fascinating behavior, in the eyes of somebody who loves to understand computation, at any one of the levels of the running time hierarchy.

I have heard the claim that P-vs-NP is the most interesting question, because it's the root node in our binary search tree for understanding problems --- the first thing we ask is whether this problem is in P or not, and then proceed with two different sets of techniques depending on the answer. The root node of the classification tree has to be the most interesting.

But this argument pales when you remember that we're really chasing the intellectually challenging cases. For many problems, a 5th grader who just learned programming can give a polynomial algorithm. This doesn't tell me anything interesting from a scientific perspective. The most interesting behavior happens right at the phase transitiong where the problem becomes hard. For some problems, it's at O(lglg n), while for some it's at O(2ⁿ).

A problem in current TCS. Of course, I cannot write a post without being provocative :) So let me state what I view as a significant problem in current TCS.

There is a field of study, namely approximation algorithms (which includes such newer branches as mechanism design), in which you can do fine without much understanding or appreciation of computation. The name of the game in this subfield is rounding LPs and SDPs, a task which requires geometric skills and discrete Maths skills, but not much algorithmic skills. Heck, many papers in the area don't even have a for loop in them! The only interesting algorithmic content is solving the LP or SDP, which few people really work on.

This has led to a hoard of TCS students with very little appreciation of algorithmic phenomena, who basically learned how to hide them all away under the "polynomial" hood. (I'm sure you've met people who are surprised at the idea of storing some forward and backward pointers between two pieces of information for navigation throughout the algorithm...)

I hope this doesn't ruin the future of our field. Once there's a significant group of such people, we could easily diverge into creating useless problems that can be solved by these techniques, and lose track of the fact that we were supposed to do algorithms and complexity. (As I said before, the field evolves based on what the field finds exciting. Another way to put it is that researchers are often in the business of drawing targets around the arrows that they manage to shoot, and I can see these new targets drifting away from the original big one.)

The encouraging bit is that the standards for success in approximation algorithms (for old researchers) still involve crystal clear algorithmic thinking. Consider for instance, the two recent algorithms researchers who won the Gödel Prize: Dan Spielman and Shanghua Teng. They moved from a major polynomial-vs-exponential result with mostly mathematical content (smoothed complexity of LP) to a much more algorithmic question, approximating the sparsest cut in linear time. This latter problem has picked up quite a bit of steam in recent years.