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

Romanian keyboards

This is a public service announcement for the Romanians in the audience.

Romanian needs 5 letters outside the Latin alphabet (ă, â, ş, ţ, î). In the dark ages of computers, we would just substitute the Latin/ASCII letter for the Romanian letter, sometimes with comic effects (consider tata=father vs. ţâţă=breast :P ). Fortunately, Unicode has been the Internet reality for quite a few years, so we should now spell correctly.

But how can we generate the Romanian letters easily? Romanian keyboards are terrible in my opinion, because they banish these highly used letters to the edge of the keyboard. The alternative I have found is a little bit of freeware called ER1. This keyboard layout replaces unused Latin letters, which are very conveniently located on the keyboard, with the Romanian letters (e.g. q-->ă, w-->ş etc). I found I was able to type at high speed in a matter of minutes.

In Windows, you can change between keyboard layouts with LeftAlt+LeftShift, so switching between English and Romanian text is extremely easy.

Searching for the right word

In a true liberal-arts school, searching for the right word may take two weeks...


Later:


Attachment:

Easter Aggregates

We celebrate the western Easter (incidentally, not our Orthodox Pascha) with news from around the world:

• via IHT, we hear the opinion of Zhang Qingli (张庆黎), the party secretary in charge of Tibet: "The Communist Party is like the parent to the Tibetan people, and it is always considerate about what the children need. The Central Party Committee is the real Buddha for Tibetans."
  
  
• Bin Laden threatens the EU for implicitly endorsing the Danish cartoons. The message features a cartoon of a spear hitting the map of Europe and blood spilling around. Very professional for a terrorist message.
  
  Sometimes, you may think the bad guys stand a chance (like, when Hitler came close to ruling all Europe; or when all the world hates the American war machine and may think Bin Laden can be excused on some points). But fear not --- the bad guys are driven by their extreme ideology, so they are bound to do something extremely stupid sooner or later (like attacking Russia, or picking a fight with mostly neutral Europe).
  
  By the way, if you're in the US or the UK, there's a high chance that you haven't seen the Danish cartoons, since the press here never actually showed them. To see what the rest of the world sees in their papers, go here. Personally, I like this one the most:
  
  
• If you're not watching the exchange rates, let me tell you that 1 EUR is close to 1.6 USD these days. We all remember the days when 1 EUR was 0.8 USD, no?
  
  It's funny how the funds, banks and Journals can get excited about the stocks going up a bit every once in a while. Guys, those prices are in dollars! A better option for your money might be a European company heading to bankruptcy.
  
  People (e.g. Muthu) sometimes wonder how to build a perfect research environment, and what it would take to move us all somewhere else (Europe). I never had a very good answer to that, but these days I often think I will not be interested in tenure in the US.