Wednesday, May 25, 2005

Durable metaphors for (theoretical) computer science

Michael Mitzenmacher writes:
I think as a field we need to do a better job clarifying that computer science is about a lot more than programming, and that the skills learned in the major can apply well in other areas.
Indeed. One of the main areas of discussion at the STOC business meeting appeared to be (I did not attend) on ways of disseminating the impact of theoryCS. The new theory advocacy website aims to be a clearinghouse of such information.

However, there is an important other angle to this whole business of demonstrating the value of theoretical computer science (and CS in general, although this post will be theory-centric). Not only do we need demonstrable examples of where theory is used in practice, but we also need a more fundamental story line for the raison d'etre of theory in the first place.

To take the example most commonly touted, the mythical 'man on the street' has probably heard of E=mc2 and quantum physics and something about relativity, without necessarily understanding anything more about it. This person, if asked, will be able to hazard some guess as to what physicists do, and how it's fundamental (in a vague way) to everything in our modern world (at least to nuclear weapons and space exploration).

But we don't have a similar story line for theoryCS.

The point of doing theoryCS is that one believes (and there are degrees of belief here) that a computation is a tangible entity. What I mean by this is that there is something almost Platonic about a 'hard' problem and an 'easy' problem; the intrinsic complexity of a problem appears to be a feature of that problem itself, independent (upto a point) of which machine we are using.
These statements are given their heft by the Church-Turing thesis and its effective variant, and even the notion of completeness, the idea that certain problems are the exemplars of what is hard to do with a certain limited resource.

I am uneasy going as far as claiming that there are 'natural laws' for computation, but the analogy is not completely outlandish. Theoreticians do believe that at the core of any computation is "a problem", and the first order of business is to identify this core problem and classify it depending on various measures of complexity (space, time, etc).

But this is not an idea that is conveyed in most undergraduate classes in computer science. In fact, this is not even an idea necessarily shared by all areas of computer science, otherwise we'd see a lot more 'problem identification and classification' than we currently do.

The idea though is crucial to providing a deeper answer to the 'whys' of computer science, in a way that can capture the imagination, far more so than a litany of applications. After all, let's face it; people don't remember general relativity and quantum physics for the list of applications enabled by them, but for an ineffable mysteriousness and beauty that surrounds these descriptions of our world.

We need to communicate that same sense of beauty that comprises the hard core of (theoretical) computer science if we want to convince people that the field is more than just programming. This is not as a replacement for the more traditional theory advocacy that we should and must do, but as a different form of advocacy that targets a very different audience, for a different purpose.


  1. It would be interesting to have a rigorous study interviewing a uniform random sample of people in the street and see what they actually know about quantum mechanics vs. computational complexity (for example).

    I think as scientists its hard for us to conceptualize the knowledge of the average non-scientist (simply because we tend mostly to talk about science with other scientists) so it might be have our intuitins checked against hard data.

    We could then devise an advocacy campaign accordingly.

    We might even be able to get NSF funding for this study;) 

    Posted by Mugizi Robert Rwebangira

  2. Perhaps, as one of the commenters on Lance's blog suggested, we should change the name of the field from "theoretical computer science" to something more down to earth ("the science of problem-solving") or more flashy ("problemology") that doesn't use the scary (and unnecessary) word "computer".

    This issue is incredibly important, but any solutions will have to deal with the cultural divide within computing between foundations/applications, science/engineering, ideas/devices, CS/IT, (CACM before 1990)/(CACM after 1990), or whatever you want to call it. The story of theoretical computer science may be almost entirely disjoint from the stories of software engineering or networking systems, just as it is from (say) the stories of signal processing or algebraic geometry. Yes, there are major overlaps, but the central metaphor—how we convince ourselves that what we do is important—is very different. We may face some resistance from the Dark Side.

    A couple of years ago, my department chair opened our weekly colloquiuum series by stating that computer science was a misnomer because "what we do has almost nothing to do with science". I absolutely agree with his statement, except for the last word. 

    Posted by JeffE

  3. A cab driver asked me what I do a few years ago. I started explaining NP-completeness to him, and he turned out to have heard of it already. That was in Boston, but it was still gratifying.

    When the Clay Mathematics Foundation announced the Millenium Prize Problems, there was some effort at making theoretical computer science accessible to non-CS people. Does anyone remember the "Minesweeper is NP-complete" result? I also saw a couple of public lectures aimed at non-scientists during this time. How well did that work (or not)? Is it something that should be revived?  

    Posted by David Molnar

  4. your cab driver was probably a cs grad ;o


Disqus for The Geomblog