Here's an example of the kind of research illustrating the gap between the priorities of complexity theorists and those of people who just want efficient algori

Here's an example of the kind of research illustrating the gap between the priorities of complexity theorists and those of people who just want efficient algorithms: It's a hard problem to approximate the volume of a convex body in n-dimensional space, given a membership oracle. (An oracle is an O(1) function that tells if a point is in, or not in, the convex body.) Is it exponential time in the number of dimensions (e.g., requiring an exponential number of calls to the oracle)? This is a fundamental question, and turns out to be important in lots of applications. The following 1991 paper: http://www.stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/Dyer.pdf http://www.stat.duke.edu/~scs/Courses/Stat376/Papers/Converg... caused quite a stir in the field. It has 380 citations. It proved, without explicit construction, that there is a (randomized) approximation algorithm that is order n^23, with a huge, and unknown, leading constant. It was totally useless in applications, but totally exciting for complexity theorists. Since then, people have been plugging away. The most recent result I can find is by Laszlo Lovasz, appeared in 2003, and shows an O(n^4) algorithm. It's also randomized, very complex, and let's just say that the constant has got to be huge also. The problem for practitioners is, you never know when all that plugging away is going to produce a good algorithm that is easy enough to implement. It it happens, it can totally change the computational landscape. The FFT is my favorite example; its discovery has revolutionized all sorts of computations.