Thursday, September 30, 2004

The Specialization of Computer Science

I heard the following from a senior economist recently.
A researcher at the beginning of his career has to please others. In order to receive a Ph.D., get a job and eventually tenure, he has to not only produce good research but research of value to others. The researcher might think that once he gets tenure he can do the research he wants, but by that time he has become so specialized it is impossible to change direction.
Looking at economics can give us a glimpse into the near future of computer science as a discipline. Though economics as a field has been around for a very long time, only since the 1950's did economics develop as a rigorous mathematical discipline. This gives economics about a 15-year head start on computer science.

When I started in grad school in the mid-80's, I could follow nearly every talk at the major theory conferences, STOC and FOCS, though I would not have followed any computer science talk which might have been true 10-15 years earlier. These days I can understand the importance of the main results of maybe half of the talks and have actual interest in only a small fraction of these. The growth of specialty conferences such as Complexity, SODA (algorithms), SoCG (Computational Geometry), Crypto, RANDOM/APPROX, COLT (Learning Theory), LICS (Logic in CS), QIP (Quantum) and so on have only increased this divide. We get less and less crossbreeding between these subfields of theory.

On the other hand, some researchers still can and do (with some effort) change research areas in theory and general computer science even after tenure. But in 15 years will we look like economics where a late change in field is difficult to impossible and soon after that like mathematics where it often takes years of graduate school just to understand the major open questions in an area.


  1. As long as P vs. NP remains open, there will be one thing that unites our field.Frustration?

  2. This is an interesting idea, Scott. How much of TCS is geared more-or-less directly toward resolving P/NP? Asked another way, if the P/NP Proof From The Book fell to earth tomorrow and was grokked by December, would a grad CS department still consider Theory applications for Autumn 2005? :) And in which subdisciplines?

    Personally, I can say that I am very interested in theory, but I don't think that P=NP or P!=NP would change that at all. Is this true in general, or is it that I do not understand the research correctly and a solution of P/NP would "sweep the rug out from under my feet"?

    Maybe I am crazy, but I find it very sad to consider that the field would fragment upon finding a formal answer to what _might be_ a pretty meaningless question.

  3. One might say that the unsolved Hilbert's problems unite all of math. But they don't, do they ?

    Although the fragmentation of theory CS is something to be regretted, it is also inevitable, and in a way is a success of individual areas at becoming richer and more advanced in their methods/problems/what have you.

    Isn't this a natural evolution of theory ? we should mourn the passing of an era, but not to the point where we try to reverse the trend.

    Maybe that's why math surveys have become so important. Like in Math, in theory we will have a (mostly) common language, the language of polytime and O() notation, and we will come to rely on surveys and other expository writing to bridge the gaps. It will become harder and harder though to have an impact across disciplines.

    What worried me more is the growing learning curve hump between quantum computing the rest of theory CS. that actually seems like a field with a very different base language...

  4. P vs NP is an important problem. May be a very important problem but what's so deep about it?

    A deep problem is one that explains a lot
    of phenomenon in nature. So formulation of NP-Completeness was deep. But, how is P vs NP deep??

    See, if you are getting obsessed by P vs NP its not because it is deep but its because you find it important! You are coming not from the perspective of interest but from your 'ego'. Andrew Wiles solved Fermat's last theorem - in what way
    did it change the field of math? I suspect not. Go with what you find interesting rather then what you consider important...