Friday, May 23, 2008

The Great Conceptual Debate

If you're a theorist and you haven't been hiding at the South Pole in the past month, you probably know about the great conceptual debate, initiated by this letter, discussed at STOC (great coverage by James), and recently picked up by Michael and Luca. In general, I found the opinions of James and Luca to be close to mine, and I much enjoyed the way they expressed their thoughts. Let me now expand on a few bits of my opinion that I did not hear somewhere else already.

Philosophy. First, we begin with a joke:

While the university is planning its budget for the next year, the Physics department puts in a request for 1 billion dollars for a new accelerator. The president of the university goes to the head of the department, and complains:
"Why can't you guys be more like the Math department? All they need is pencils, paper, and waste-paper bins..."
"Or better yet, why can't you guys be like the Philosophy department? All they need is pencils and paper."
The great danger that I see in our current trends is that we may be moving towards a philosophy department (and we don't want that, if for no other reason then because we don't envy the funding and respect they get).

With every new model from a new field that we understand only partially, and with every problem open to endless interpretation over a beer (like modeling communication with aliens or social networks), it becomes harder and harder to say what should make it to the waste-paper bins.

A theoretical field is meant to generate depth, and we should never forget that depth is our only strength. I would say that in TCS, the conceptual contributions we make when introducing new models are nothing compared to the conceptual contributions we make in developing proofs.

The only place where we can make a difference is in developing brilliant ideas for hard problems. We will never beat more practical fields at their favorite game (modelling many different problems intelligently, and recasting known theoretical ideas in that framework). And this is not what we should be trying to do.

I should emphasize that my point is not חדש אסור מן התורה. We need to adjust to a changing environment. But the rate of introducing new problems should be kept very low (I would say, even lower that we have it now), to give us time to concentrate on deep solutions. And we should be wary of problems that are an endless modelling game.

The AI lesson. If the Philosophy department seems too far away, let us focus on something across the hall from us. Do you remember the period when AI was obsessed about the "great questions," like what intelligence really is, what knowledge is, what the universal principle is for dividing preprogrammed and learned behavior, etc etc? I was not around the CS departments in the 70s, but I hear theorists were not too deeply respectful of those perennial ideological debates.

Thus, I will not be among the people to welcome papers on a computational view of consciousness, communicating with aliens, etc. This is not because I share the sadly common opinion that this is junk research (see comment 5 here, ahem). Saying that this is junk is typical theory snobbery, and is the last thing we need to be saying. (Plus, some of the guys who were in AI 30 years ago are our colleagues, and I actually like some of those people.)

These things are a valid topic for thought --- but I just don't think we should be the community thinking about them. Theory has a huge advantage in being concrete and objective, inheriting that immortal coldness of Math. I don't want us to lose this advantage because we find questions about consciousness and aliens entertaining. There are other forums for these questions, which also have more experience on how to deal with scientific publication on such issues.

The conceptual letter. After so much debate, dissecting the conceptual letter feels like dissecting a cadaver, but for completeness' sake, here goes:

1. As everyone observed, the conceptual manifesto shot itself in the foot by being too vacuous. What is it really saying? Of course we all want simple and elegant proofs for major open problems with great practical applications. But what is this conceptual business? Since I don't like very under-specified problems rife with ideological debates, I shouldn't be the one trying to define what a "conceptual" paper is. Unfortunately, the letter doesn't do a great job either.

2. As many people have pointed out already, purely conceptual papers are not so easy to gauge, whereas author names are. Making an official push for more conceptual papers can easily politicize the process and give a lot of weight to big names. I wish the signers of the letter (most of them highly influential people) had thought about this more carefully when they were adding their names to the list.

I am told that this effect is visible even in STOC'08. Some people are making statistics on the "big name effect" at this conference (hopefully to be released soon), and I am told numbers look bad compared to previous conferences.

3. As you already know, I disagreed strongly with some decisions by this STOC PC, and I am not the only unhappy person. Unfortunately, the part where the letter is praising STOC'08 is one of the few unambiguous ones...

4. Confusing the notion of concept with the notion of new model is major mistake that we are making. Great concepts are developed all the time in new, beautiful proofs of important theorems. To me as a theoretician, these concepts seem much more important and valuable than modelling a problem correctly.

Trying to distill concepts, explanations, taglines etc in what we have done is a great goal with major impact to our funding, recruiting, status among disciplines etc. But let's spend our energy finding a nice description for some deep understanding that we already have, not searching for some theorems that are an excuse for nice descriptions and taglines.

Referee reports lie big time, because people think being conservative and polite is more important than being honest. In my short experience as PC member, this was painfully obvious. Just because the PC said your paper is not technical enough doesn't really mean this is why they rejected it. It's just something they can say easily, as opposed to attacking your model. I wish PC chairs were much more active in combating such reviews.

That said, I do agree that we enjoy technical difficulty too much. It has happened that we accept a new problem when somebody comes up with a complicated algorithm for it, and then we reject the 2nd paper that has a simple and better algorithm. This is entirely unacceptable.

Yes, we were wrong about some crypto papers in 1982. But mentioning it so often in 2008 is like using the original sin to explain sexism. (Not to mention that the connection drawn to these papers seems wrong, as Luca aptly explains.)


Anonymous said...

chadash asur min ha-Torah (חדש אסור מן התורה), "The 'new' is forbidden by the Torah," originally referring to new (winter) wheat that had not been sanctified through the wave offering culminating in the Counting of the Omer in the Temple in Jerusalem, now broadly understood to mean "innovation" in general.

Anonymous said...

Of course, we know that you probably weren't born in 1982 (or if you were, you were just starting to learn how to walk), so it is understandable that you find it hard to relate to anything that happened back then. To the rest of us who remember 1982, however, it is very unfair and offensive to compare 1982 events to Judeo-Christian creation myths and fairy tales.

Mihai said...

STOC/FOCS PCs are not a secret group dominated by a few dons for half a century. They are very heterogenuous groups, involving new young people each time. They are dominated by trends in collective group thinking, if anything.

It is exceedingly likely that trends in group thinking changed dramatically since 82, so any point, valid or not, about our misconceptions back then has little relevance in current debate.