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.

5. 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.

6. 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.

7. 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.)

STOC'08 update

My call for confirmation worked. I got a second member of the FOCS'07 PC to confirm that 15 rejections appeared in STOC'08. So pending new developments, let's treat this number as roughly correct.

The next steps are to:

• also get a 2nd confirmation for SODA'08.
• look at previous FOCS / SODA, and see how many rejects appeared in next STOC to see whether the numbers are really different. If you were on a previous FOCS / SODA PC and would like to help anonymously, please let me know... I think these statistics would be an interesting factoid for everybody, regardless of what we think of the current STOC.

To clarify where I'm going with these numbers: my goal for now is to simply get them out. I'll let you, the community, interpret them. My gut feeling is that the numbers are high (15 is roughly a fifth of the program!). Coupled with the unobjectionably low count of algorithmic papers, I think there are good reasons for discontent.

Jobs

Normally, Lance has a yearly post asking where people around the theory world ended up at the conclusion of their job search. But this year I'm going to organize a coup :). Please leave a comment and let us know where you or your friends are going next year, if graduating or changing jobs. Many decisions are still to be made, but let us know when you do decide.

For now let me begin with my personal story. The hiring season is finally over for me. It's been a very hard few weeks (deciding what I want to do), and a much harder day telling people about it. I really look forward to getting back to research after this.

The outcome is that I am going to AT&T Labs, the fittest descendant of the legendary Bell Labs and seemingly a good place to work towards a Nevanlinna prize ;). The lab has certainly had its share of corporate nightmares in the past decade, but it seems it is coming back as a major force in this confused landscape of corporate research.

Next year proper, I will be at IBM Almaden, on a Raviv fellowship. I think IBM Almaden has one of the most amazing groups in theory from the US, featuring some 5 theory hires in the past few years, and some true all-time classics (including an almost mythological figure of concrete complexity, Miki Ajtai). The dedication of the relevant people there to "sell" a theory group to the corporation is truly admirable; theory would not be the same without such efforts. It was very difficult for me to reject a permanent offer from this group, but in the end ATT was slightly better for personal reasons.

I am one of those people who treat labs as a long postdoc, and I think my path will be to return to academia after a number of years. For a second, declining university offers to go to labs felt like a step into the void. The decision was not particularly easy, since I had to turn down Georgia Tech, a place with an admirable dedication to theory, who many see as the big rising star in our field; and UCSD, a place with a truly captivating personality, a disarming feeling of friendliness, and some very ambitious plans for the future (I liked to call it the Google of academia).

Why did I choose labs? Hard to say... I could use a few years to work on some problems that I really want to solve. I value industrial experience, and (I think) I'm interested in networking -- SIGCOMM / SIGMETRICS kind of stuff. Things are too dynamic now and I want to keep my flexibility and avoid the big commitments that a university job requires. And, in the end, some of the values I admire the most are courage and ambition, and I should stick to them now.

STOC 2008

STOC 2008 is coming up in a few days. Though I think it is important to attend STOC/FOCS even when you don't have a paper, I was simply too disappointed by this conference to go.

Scrolling down the list of 83 accepted papers, I could not help marvel at the almost-complete lack of (non-approximation) algorithms from the program. Alas, this was not really for lack of submissions. I know of several papers that were submitted, and in my opinion, should have been very easy STOC/FOCS accepts. (Since these are not my own papers and not yet published, I cannot really talk about them.)

Quite likely, the heavy bias against algorithms was due in part to the composition of the PC, which essentially contained nobody in the area. But another way to view it is that algorithms were collateral damage in the raging war on whether it is conceptually more important to approximate the Stochastic Traveling Dog and Pony Problem with Piecewise Linear Costs, or the Games that People Don't Play^TM. (IMHO, the best papers from these fields always got in; it is only the marginal papers that need a boost for being "conceptual"... But that is a topic for another discussion.)

Based on the rantings that you can hear left and right (and, during this spring's interviews, STOC'08 was a popular topic of conversation), it seems the war might have taken its toll on the quality of the conference as a whole. Reportedly, this STOC contains about 10 papers rejected from SODA'08 and 15 papers rejected from FOCS'07.

If these numbers are true, there is serious reason to worry about what this conceptual drive is doing to our academic standards (no, we don't really believe that all these papers were improved substantially from the past submission...) To quote a PC member from a past conference: "These papers were not rejected for being too conceptual, they were rejected for being too weak."

If you were on the SODA or FOCS PC and would like to confirm these numbers or post your own count, please leave an anonymous comment or send me personal email. The latter is preferable because it makes the message trustworthy. I will post your recount, but your identity will remain forever secret.

Christos Anesti

Christ is Risen! to all the Orthodox out there.

At MIT, we use the opportunity to cook some Romanian food and have a party (and an after-party at my house, it seems). As prototypes of our post-communist generation, we don't really believe in anything, including religion. But it is a cool opportunity to get together.

To celebrate this atheist Orthodox party, let me share a timely joke told tonight.

Yitzhak is very sad: his son converted to Christianity. His friends advise him to talk to the Rabi.

He goes to the Rabi and tells him his story.

The Rabi says: "You know, Yitzhak, I had the same problem, and I asked God about it..."

"And what did God say, Rabi?"

"He said: You know, Rabi, I had the same problem... "

Incidentally, I flew back on Friday night, and I'm flying away in the morning... I promise to get back to some blogging in about 1.5 weeks, when my interviews and visits are over.

SWAT'08 accepted papers

Via Dense Outliers, the SWAT'08 list of accepted papers is out.

Evidently, if your paper was rejected, it is because *I* thought it was too good for this worthless conference.

Now seriously... if you've never been on a PC, the way these things get decided is the following:

• people vote on what they want to review, by reading the author names (primarily), the titles, and maybe the abstract.
  
  
• papers get distributed, and PC members may outsource them to external reviewers. I think it is a good idea to outsource the paper, because an expert might see things that you're missing (like "the main idea appears in this other paper that is not cited"). Alas, for some papers the class of experts on the topic coincides with the list of authors.
  
  
• in addition to outsourcing the paper, you absolutely should read it yourself, to adjust the paper evaluation based on the average level of the submissions. Outsiders can easily overestimate or underestimate the level. I got comments like "this paper is crap, but it's good enough for something like SWAT" (for some terrible papers that we trashed very quickly), or "they give a better running time for an important problem using novel ideas, so I'd say it's a borderline accept" (for some of the best papers at the conference).
  
  
• after all comments get uploaded, a blogging-style discussion starts, by leaving comments for each paper. Yes, ultimately, your fortunes are decided by some sort of blogging. And no, the comments for your paper are not much better than regular comments on blog posts, though they are more polite because people are not anonymous.

Rankings

The well-known (and very often criticized) US News Rankings have been released this year. Here are the ranking for computer science, and specifically for theory. Apparently, you don't need an account to access them.

As we all know, it is a bad idea to take these ranking too seriously, but at least they contain a list of the top schools in some order. For the theory rankings, I would diagree with the position of Stanford (too high) and Princeton (too low).