Tuesday, April 18, 2006

The vision thing

Suresh asks what I think about "vision" in theory.

I have an instinctive (and irrational) dislike for this use of the word. It evokes to me images of people who are full of themselves, who say things like
"In the information age nonsense nonsense for the 21st century."

and who think that research can be planned in advance.

Thankfully, the theory community is quite immune to this kind of attitude. As theoreticians, we know that the only answer to the question "what will the great advances in theory be in the next five years" is "we don't know," because if we knew, we would be making these advances now, it would not take five years, and they would not be such great advances after all.

I shall still avoid the use of the loathed word, but I want to comment on the importance, for theoreticians, of perspective and taste.

I think it is very useful, for a theoretician, to develop her own "ideology" about theory: to get a sense of what she thinks are the long-term goals of the fields, of how a particular research program fits into these goals, and of what constitutes helpful progress. Without this perspective, one risks to end up studying a generalization of a special case of a problem related to a question that ... and so on.

It is also extremely important for the community itself to go through the process of defining such goals, and to explain the way in which current research fits them. Indeed, a story of goals understandable to a general educated public, and of the way we are making progress towards them, is very useful to funding agencies, where people charged with making difficult choices about assigning funds to different areas need to know what we are doing and what we need.

Here I should add two things. One, is that this "narrative" about what we do is not something that one person can sit down and write up in an afternoon, it is an extremely difficult, and never-ending, task in which the entire community must be actively involved. (See theorymatters.org.) The other, is that there need not be only a single way to think about theory, its motivations, and its goals. On the contrary, it would be a disaster if everybody was thinking in the same way, and several important results have come from the perseverance of researchers that had gone off in directions that others thought not promising. Presumably, there are at least two or three main, complementary, "ideologies" about theory, and all are worthy.

I have talked about the "strategic" way of thinking about research. At a "tactical" level, every research area has an infinite, or at least very large, number of well defined open questions, and a researcher needs "taste" to distinguish interesting questions from uninteresting ones. This is a particularly sensitive issue in complexity theory, where results typically don't have "applications" in any immediate practical sense. I think that there is a common misconception that complexity theorists like results that are difficult at the expense of results that are useful.

To understand complexity theorists' taste there are two things to keep in mind: that all the important open questions of complexity theory are far beyond our current techniques, and that the most exciting discoveries in complexity have been unexpected connections between different problems and surprising equivalences between models of computation. For both reasons, complexity theorists always look for new techniques and new questions, and a good problem is a problem that is understood to be just beyond (our understanding of) current techniques, and a good model is one that is not (known to be) equivalent to other models, and that captures interesting problems. This is, in part, the reason for the excitement around unique games and the reason why people seriously study the power of constant-depth circuits with mod-6 gates.

When a good question (one at the edge of the reach of known techniques) is solved, the proof is often very difficult, because the authors had to create from scratch something different, and often they did so in a way that was not the prettiest possible. Over time, however, the proofs of almost all important results in complexity theory have been cleaned up considerably. And when an important question is settled with a proof that is both novel and simple, I think everybody cheers twice.

Like for the broader perspective, I think it is very useful for a community to articulate its taste, to be able to explain why certain results and certain problems are important. This is even harder. At a gut level, I always know when I like something, but I find it extremely difficult to explain why, if someone asks.


  1. Blogger Suresh Venkatasubramanian
    4/18/2006 07:50:00 PM

    excellent. that's a great articulation.

  2. Anonymous Anonymous
    4/18/2006 10:50:00 PM

    common misconception that complexity theorists like results that are difficult at the expense of results that are useful.

    Does this really exist? Somehow I often run into people guarding against this "misconception" but rarely (if ever) come up against the misconception itself (at least from within the theory community).


  3. Anonymous Anonymous
    4/19/2006 07:18:00 PM

    clearly since no one came forward to claim this misconception, it does not exist.

  4. Blogger Suresh Venkatasubramanian
    4/19/2006 09:54:00 PM

    well Lance once commented on this in a post a while back on how to write papers for STOC/FOCS. he pointed out that obscurity and apparent technical complexity is often rewarded.


Post a Comment

<< Home