My daily dose of depression

Yesterday’s Times ran an essay by Steve Lohr, based on speeches about the future of computing given by my former teachers Richard Karp and Jon Kleinberg. Though most of the essay is welcome and unobjectionable, let’s look at the first two paragraphs:

Computer science is not only a comparatively young field, but also one that has had to prove it is really science. Skeptics in academia would often say that after Alan Turing described the concept of the “universal machine” in the late 1930’s — the idea that a computer in theory could be made to do the work of any kind of calculating machine, including the human brain — all that remained to be done was mere engineering.

The more generous perspective today is that decades of stunningly rapid advances in processing speed, storage and networking, along with the development of increasingly clever software, have brought computing into science, business and culture in ways that were barely imagined years ago. The quantitative changes delivered through smart engineering opened the door to qualitative changes.

So, here are the two options on offer from the paper of record: either

1. computer science was finished off by Alan Turing, or
2. “stunningly rapid advances in processing speed, storage and networking” have reopened it just recently.

Even among the commenters on this post by Chad Orzel — which Dave Bacon forwarded to me with the subject line “bait” — awareness of any third possibility seems depressingly rare. Judging from the evidence, it’s not that people have engaged the mysteries of P versus NP, randomness and determinism, one-way functions and interactive proofs, and found them insufficiently deep. Rather, as bizarre as it sounds, it’s that people don’t know these mysteries exist — just as they wouldn’t know about black holes or the Big Bang if no one told them. If you want to understand why our subject — which by any objective standard, has contributed at least as much over the last 30 years as (say) particle physics or cosmology to humankind’s basic picture of the universe — receives a whopping $5 million a year from the NSF (with even that in constant danger), look no further. 15 Responses to “My daily dose of depression” 1. Anonymous Says: You say the general public doesn’t know these ideas exist. In physics, the general public knows these things because of people like Weinberg, Hawking, Greene, Sagan, Penrose et al, who have all written terrific popular books on deep ideas in physics. Has anyone done as good a job for theoretical computer science? I’m probably forgetting something, but the best things I can think of are books like Hofstadter’s GEB. It’s a nice book, but the relationship to TCS is somewhat peripheral, and in any case I don’t think it’s as suitable for the general public as the works by Weinberg et al. Michael Nielsen 2. Scott Says: Has anyone done as good a job for theoretical computer science? No, they haven’t. Which reminds me of something I need to finish… :-S 3. A little night musing Says: Oh, man. The general public doesn’t even know these ideas exist. What shall we do? [No jest, this. I’m concerned. I mostly teach CS majors.] Meanwhile, all problems in pure mathematics are essentially solved, as per what I get from the press and, alarmingly, my students. Modulo, of course, conflicts over priority for the Poincare conjecture. I might just get depressed myself, were I not so busy trying to prove the Riemann conjecture. 4. Anonymous Says: I’m happy to admit that I don’t know anything about “one-way functions and interactive proofs.” So, in what sense has theoretical computer science contributed more in the last 30 years to our basic understanding of the universe than particle physics or cosmology? (Despite the fact that I’m a cosmologist, I don’t doubt your statement — I’d just like to be able to explain it in public.) Sean Carroll 5. Anonymous Says: I agree with anonymous 12:24. I know (approximatly) nothing about theoretical computer science, and find it hard to accept that it “has contributed at least as much over the last 30 years as (say) particle physics or cosmology to humankind’s basic picture of the universe”, but will accept it if you would care to explain. I may just be showing how ignorant I am of this field, but to me the standard model (ok slightly more than 30 years…) or ΛCDM (Lambda-Cold Dark Matter) is more significant to our “basic picture” of the universe than showing that PH is contained in IP (thanks wiki)(my examples are certainly skewed). I stand to be educated. 6. Aaron Says: As per a fellowship application essay I just wrote, I think that a good way to impress onto the general public the fundamental nature of the theory of computing, would be to describe it as physics. Physics studies fundamental quantities of the universe and the forces that act on them. So does computer science: It studies information, and the force that acts on it, computation. I think its important to sell the fact that these things have fundamental and universal properties, independent of their instantiations, and I don’t think this is widely appreciated. It should be easy to romanticize this stuff! As a young field, the cool open problems are still easy to state. Finally, the book should not have the phrase “Computer Science” anywhere in the title. Thats a terrible name, because it has the word “computer” in it, and people associate buggy software and system administrators with computers. 7. Greg Kuperberg Says: In my view, the mathematical community is always available as a shelter for good theoretical work that is not properly understood by the rest of the world. If you cast it as mathematics, then you no longer have to offer a silly song and dance to naive journalists or their counterparts at funding agencies. You no longer have to face the hostile question, “it looks interesting, but is it really physics/computer-science/biology/etc.?” You can instead place your own aesthetic of what is important inside the usual mathematical aesthetic. I am not saying that the theoretical CS community should just give up on either the Carl Sagan approach or the Silicon Valley approach for getting money. It is better to have more funding than less funding. My point is that if you ar e willing to join the mathematicians, or at least act like the mathematicians, you can still have a good life with epsilon funding. Look at Peter Shor and Hendrik Lenstra, for example. They are first-rate computer scientists with mathematics appointments. You also see the same thing with string theory. We have two string theorists (of a sort) in our math department. 8. Anonymous Says: The choice to focus on computing as a science is an arbitrary decision. Computers are a man-made artifact after all. Consequently, as I have argued earlier, we could also view computing as more of a creative endeavor with construction of novel applications as the main focus. Maybe this would be easier to sell to the general public. 9. Anonymous Says: I would gladly bet$100 for every $1 someone else puts up that if Hendrik Lenstra were asked whether he considers himself a mathematician or a computer scientist he would a) laugh and b) say he’s a mathematician. He does however have a side interest in some computational issues. 10. Polly Nomial Says: When writing the supremely popular book on computer science, don’t forget to use the magic noun “elegance,” made famous by J. von Neumann. This word has amazed and fascinated millions of laymen for decades. They wonder if it is the mere symmetrical balance of an equation, or something occult and wonderful. 11. Greg Kuperberg Says: I would gladly bet$100 for every \$1 someone else puts up that if Hendrik Lenstra were asked whether he considers himself a mathematician or a computer scientist he would a) laugh and b) say he’s a mathematician. He does however have a side interest in some computational issues.

I’m sure that he does think of himself as a mathematician. I didn’t mean to misrepesent the man. But that doesn’t contradict my point. What you call his side interest in computation is still first-rate TCS.

> Has anyone done as good a job for theoretical computer science?

No, they haven’t. Which reminds me of something I need to finish… :-S

I second the nomination for Scott Aaronson for the post of Computer Science Evangelist to the World! As an OR-PhD in industry, I greatly appreciate your blog as a means of reconnecting with my complex academic past. Keep up the great work!

13. Scott Says:

Thanks!!

14. Kea Says:

Good one, Scott. Some physicists are on your side.

15. Kostya Anenkov Says:

I am Zoidberg!