Correctness, conference ranking, etc

I missed a few events on the blogosphere, because I've been on the campaign trail (aka interviewing), but also because I'm not such a regular reader these days. There was a bit of follow-up to my now-famous post on correctness and SWAT (including whining in emails to the PC chair, which I find hilarious --- but YMMV).

Daniel Lemire writes a post essentially saying that top-conferences are for trend-followers who can't have an original idea. Commenters pick on the opportunity to congratulate themselves for all papers they couldn't get into top conferences (after all, those had truly original insights).

Yes, we do have a bit of trend-following and bias towards some topics, but I like to think that is an unfortunate inefficiency in the system, not the model itself. In any case, until we get the perfect conference system, accept the following reality: top conferences give your ideas a broader audience, generate more following, and make life easier for you in terms of funding, jobs, etc.

So for those of you who think you are the hot shot of hot shots and the first to walk on water in 2 millenia... (and I truly hope most of you think that, since my readers come from a community doing advanced research)

... after you have managed to solve the most important problem on Earth, please accept another challenge: that of explaining to the rest of us why this was the most important problem on Earth, and why we should accept your papers. It doesn't need to work from the first attempt, but eventually your goal should be to get your research accepted in the canon, and hence to top conferences. (Guys who walk on water tend to get attention eventually...)

I will not deny that this is often a serious challenge; most times I feel I am up against the current at STOC/FOCS. But we are living in times of extraordinary activism in research, and if you're lazy about taking on the dissemination challenge after solving the technical challenge, you will soon find yourself in the middle of a research community that is just a wrong fit for you.


Michael Mitzenmacher wonders about the role of conferences, and what our stance on correctness should be. I reiterate my point the conferences are for dissemination, and for the very related goal of marking how important some research contribution looks in the eyes of the community. Journals are bad at that, unless we are willing to revamp the system:

• they have slow turn-around time, in part for an unavoidable reason (correctness checking)
• the paper is not compared against a sample of many papers, rather it is evaluated by a non-anonymous editor
  
• the paper is seen by 1 editor (from a small fixed set), and 1-2 reviewers. In a conference, we have a permanently changing set of people, 3 of which look at your paper, plus a few external reviewers.
  

Of course, conferences are not perfect, but it seems more productive to fight the problems than to trash the whole system.

Now if conference = badge of quality, what should you do about correctness? I am a big fan of the allowing papers to begin with "This is an extended abstract of a paper that has just been accepted to journal ..."

Of course, this mechanism will not be necessary for most papers, but it fixes a big flaw in the system: how to get dissemination/the quality badge for a result which does not sound 100% plausible, and is not too easily verifiable.

Job talk

Here (PPTX) or here (PPT).

Of course, most of it is in the delivery. If you want to hear it first hand, you know how to invite me to an interview :)

Conferences

Since I am asked to clarify my opinion on conferences, here goes...

1. Efficient dissemination

We have many, many researchers, who publish many, many papers. We don't write good surveys for most things, and certainly we don't keep them up to date. How do we navigate the ensuing madness in a somewhat efficient manner?

Well, we decide to rank some directions as more central to our pursuits, and we start judging some works as more important in those directions. We open some publication venues where we try to select only top contributions in the top directions, and create incentives for people to publish there (so we can ensure the venue gets the top quality stuff).

Then, if you want to stay up to date on some important directions, you only have to follow the big publication venues. If you're trying to stay up to date on directions not judged important, it is still hard, but remember, we're kind of trying to dissuade you from working on those directions! (God forbid, we're not stopping you, but you can't optimize in all directions simultaneously.)

Of course, what we think is cool and important is very open to interpretation, and essentially a social phenomenon. When two poles are forming in a community, they will each designate another venue as the cool place to publish, and the communities splits. It seems this is happening with STOC/FOCS versus SODA. To some extent, this is unfortunate, and to some extent, it is unavoidable.

Purists who reject rankings of conferences (what makes you think SWAT is less cool than SODA!) are the equivalent of anarchists in political thinking, who think we don't need to try to generate social efficiency by some central mechanism. In many cases, they have valid objections (and I have often been labeled an anarchist, in the political sense). But I think it is hard to take the dogma entirely seriously.

If you've submitted a cool paper to a non-top conference, don't worry too much. It will "make it" eventually (e.g., our data-structures course gave some good coverage to a very cool paper from SWAT, by Rasmus).

But remember that you've just generated some inefficiency for everybody. We will hear about your result later, feel less motivated to read it, and your recognition for having come up with the cool idea will be slow in coming.

If you regularly submit cool papers to non-top conferences, you should realize you're making your own life harder. Really, you're not going to single-handedly change the perception of the conference! Don't fool yourself. What you may be doing is allowing the community to forget about your favorite research directions (so it kind of "drops out of status"). You're also making life very hard on your students, a few years down the road.

Like I said before, how we evaluate each other's work is in large part a social phenomenon. Make an effort to keep your favorite area "in the news," even if this means taking some occasional rejections from big conferences. Presumably, you've spent a lot of effort solving something you care about. Spend a bit of effort in making it known, even if it's out of the way.

People don't think your results are cool? Start giving some talks. Write a survey. Write better introductions. Blog. Implement and show them how cool it is. Whatever, just don't hide behind statements like "a SWAT paper can be even better than a SODA paper." Yes, nobody said it can't. That wasn't the point.

2. Conferences as a measure of your quality

The root of all evil is that conferences are being used to measure your quality as a researcher. This really tends to piss people off, and trigger emotional reactions like "wait, but SWAT is a really good conference, my paper there is great." If you've read the above, you'll notice nobody said your paper is not great. It's just that it's great for reasons other than the label.

But while you're trying to shoot down ranking researchers by conferences, understand that at some point you just absolutely have to be ranked (hiring, promotion, getting a grant, getting a prize, students deciding what university to go to etc etc etc), and consider the alternatives for such a ranking:

• the idiot who speaks most, is affable, and sucks up to the big shots, wins despite the fact that he's not producing science at the same level you are.
  
  
• the dean has to rank you by reading your papers. The guy who writes the boldest unsubstantiated and ridiculous claims in the abstract wins. Your deep technical idea is not appreciated because the dean doesn't have the context of your subfield, nor the time to read your paper in detail.
  
  
• the guy who can get the best recommendation wins. The guy whose adviser writes on every other letter that this is the best student to come out of his university in the past 20 years wins. (Oh wait, that might not be so far from actual fact...)
  
  
• we rank people by number of publications, appearing anywhere. Science stops because we all stop thinking and start writing.
  
  
• we rank people by journal publications. Journals are, and must be slow in theory (we're presumably checking correctness). This makes it unreliable for comparing graduating students, who presumably have 1-2 journal publications at best. Even worse, remember that journal acceptance is determined by one dude (the editor), who's not even anonymous, based on some inconclusive statement from another dude. Conferences have several people looking at your paper. Even better, they get to look at a large sample of papers, and have a constraint on the number of papers accepted, which makes the decision more well-grounded.
  
  The purist objection is that we give credit for unrefereed work. But remember:

1. journals refereeing can and has failed to spot errors;
   
2. if your paper turns out to be wrong, you lose a whole lot more than the credit you temporarily got;
   
3. if there are doubts about correctness and you haven't published a journal paper in X years, credit kind of vanishes;
   
4. if nobody cares enough to read your paper and spot a mistake, you weren't getting any credit to begin with.
   

If you're at a point where ranking is irrelevant to you, congratulations! You are free to concentrate on science, and ignore this nonsense. But you should still make some effort to submit papers to the right tier in the conference hierarchy, to make it easier for the rest of us (see above).


3. Publishing papers "somewhere"

There are a few good reasons to submit papers to a non-top conference:

• you have an intriguing idea, but you don't know how to achieve anything great with it. You want to tell it to people --- maybe somebody is inspired, and you work together to do something greater.
  
  
• you have a topic that is not making it to top conferences, but you think is cool and deserves more attention. You hope that people in the audience will be impressed, and once the paper is published, it will slowly gain attention and signal a return of your cool topic. And you've already done the other things, like give talks, write surveys etc.

There are a few acceptable reasons, but we should really work to minimize those:

• you need a paper to travel to the conference, but your reason to travel is actually to meet the other people there (a very worthy goal). Maybe your grant agency doesn't let you travel otherwise, or maybe you need an excuse for your class / family / etc.
  
  
• you've worked on something due to irresistible curiosity, but it didn't turn out to be great. At the same time, you're kind of aware that you need to pad your CV.

I admit that I totally understand this last point. My papers outside STOC / FOCS / SODA / SoCG / ICALP were not great (not saying you should believe my papers in STOC /... were all great; I liked them, but hey, I wrote them). Why did I publish the others, in non-top conferences?

Well, I did work on them (sometimes quite a bit), so I felt the need to write them, and put them somewhere.

The alternative was putting them in a journal or on arXiv. But a journal takes too much effort for something non-great --- not worth it. On the other hand, arXiv makes people nervous. The fact that I have a bunch of papers in "refereed" and non-bogus venues make the hiring committees more relaxed. I expect I will be submitting a whole lot more to arXiv when I get more senior.

But the wrong thing to do is fool yourself that you will build a great career by generating enough papers at medium-level conferences (or even worse, pressure people into believing that you've had a great career doing that). You may get some mileage out of aiming for medium-quality results, but it won't be a great career.

An even worse (and dangerous) thing to do is to try to develop a bad conference into a "community" centered around mediocrity and making its own members feel good about themselves. Fortunately, we've at least kept the algorithmic conferences safe in this regard. I think essentially everybody agrees that SWAT/WADS/etc are not communities distinct from SODA.

4. Yeah, but how do you rank conferences?

I'll post about this in a few days, since commentators seem to care enough to ask. Yes, I know I'll be flamed at, and don't care all that much. If you're honest to yourself, you know my opinions are not too far off the mainstream; it's just that I tend to express them more directly.

Social Aspects of Blogging

Whenever you write something that contains a number of paragraphs and tries to have some kind of point, and you see a flame-war starting about one word in the writing (which by definition is misinterpreted because it's taken totally out of context), you remember how weird people are on the Internet.

People who in live conversation can't articulate more than a few ambiguous statements while struggling hard not to look at you --- well, all of a sudden these people develop big and aggressive Internet personas, they start having strong opinions etc, of course all expressed under the strict veil of anonymity.

And there are the entirely normal, decent people, who still can't help flaming on the Internet. After all, in person and non-anonymously, there is a higher cost to jumping at someone's throat, and you stop and think --- did I actually pay attention to what he's saying, did I try to find the point behind the statement as opposed to jumping at form? Anonymously, on Web 2.0, the cost is null, so there's not much incentive to stop and think.

No matter what you think of my own opinions (which of course are hardly new or concealed from the general public), you will agree with me that it is sad to see statements that begin with "You are entitled to your opinion," and end with:

You really ought to pay more attention to filtering out your ambition-induced half-baked biased perceptions about the world you are privileged to have around you.

Dear anonymous commenter, sorry to say, but this sounds too much like a 5-year old with tears in his eyes. I can't believe you're wasting so much mental energy getting so worked up over word-choice in a blog. Come on!

The same goes to whoever is writing detailed meta-theories on what Mihai actually thinks and says. Don't you have better things to do? I'm actually sorry to waste your time on this --- especially since it's likely you're totally decent people in live conversation, whom I might actually enjoy talking to.

I, for one, have better things to do than agonize about how to make my posts misinterpretation-proof. If you continue reading, which by the way you don't have to, then you implicitly agree that things will be rough around the edges.

When I originally started blogging, one of the motivations was that I could communicate a message much more effectively. That sort of works for technical issues, but I am now convinced that it mostly fails for "social" issues. The cost of getting annoyed over the Internet is so low, that everything degenerates into useless quarreling, which changes few opinions. In addition, ignoring whatever doesn't quite match your own perception is very easy. In the best case, you remember that "Mihai thinks that," but you never fully internalize the argument as in face-to-face discussion.

So, as I have done for several months now, I will limit social commentary on the blog. Of course, since I never take principles entirely seriously, you can be assured that personal opinions will pop up every once in a while.

Correctness?

I am experiencing the joys of being on a Program Committee (in this case SWAT'08).

• famous person A submits a paper claiming an interesting result. The writing is bad.
• famous person B, tricked by yours truly into refereeing the paper, claims said result is wrong.
• my principle for (in)correctness claims is to contact the author directly.
• A responds (retaliates?) with a link to a 40-page full version.
• B reads the full version (I guess it's personal by now), and sends back a detailed meta-argument for why the proof is wrong.

In the end, there's no hope to referee the full version and find an actual, concete bug (if one exists). So we're stuck with general arguments.

I am told to write a negative comment based on the paper being poorly written, and not mention anything about correctness. But somehow, washing my hands of the paper is not quite my style...

The politically-correct (PC?) alternative is to convince the authors that the result is too hard/long/etc for the conference, and they should submit it to a journal where complete refereeing is feasible


Oddly, this reminds me of freshman year, when I was starting in theory. When I heard of conferences and journals, my natural assumption was that papers would just be published in journals, and the best would be invited to conferences (soon after publication), as a label of quality, and to allow quick dissemination of important ideas. I remember a very confused Alex saying "I really mean, they do it the other way around."

End of Trip

After almost 3 months, I'm back to MIT.

I flew out of Luxemburg this morning, biked to Hague for lunch with a high-school friend, and now I have a few hours before attending a big Romanian party at MIT. Life is good.

Since I mention Luxemburg, I must add that I found it a remarkably beautiful city, even compared to the big European classics. Definetely worth visiting, especially for those of you who occasionally go to Dagstuhl (also note that LUX is significantly closer than FRA!)

At Dagstuhl, I gave two talks (Onlinifying Ian and Hard Data-Structure Problems), had enlightening conversations, but above all, I presented my new Romanian outfit:

(Picture courtesy of Sariel.)

The border-control dog seemed horrified by the smell of my baggage and disappeared as quickly as it could, dragging the attendant with it. I am left guessing whether it felt some faint smell of wolf or sheep blood that we cannot sense.

Talk, Univ. de Vest, Timisoara

This Friday, February 15, I am giving a talk at Timisoara, hosted by Gabriel Istrate. The talk is roughly an overview of the world of dynamic graph algorithms (no background assumed) --- what are the milestone results, the current research, and the big challenges for the future.

When it comes to current research, I will understandably be biased towards my own work, and will talk primarily about:

• how to generalize graph bridges to understand multiple edges going down (this paper with Mikkel Thorup). Big open problem: worst-case bounds.
• how to handle node failures, not just edge failures (this paper with Timothy Chan and Liam Roditty). Big open problem: handling node failures better and for more queries.

Formal details for those who want to attend:

Locatia: Universitatea de Vest. Sala 045C (Institutul e-Austria)
Ora: 10:00 am (vineri, 10 februarie)
Titlu: Algoritmi pentru grafuri dinamice
---
In multe aplicatii naturale, grafurile cu care avem de-a face au o structura dinamica: conexiunile (muchiile) dintr-o retea de calculatoare se pot strica sau repara; o configurare gresita sau un reboot poate scoate din folosinta un router (nod in graf); etc. Aceste cerinte au dus la un studiu intens al algoritmilor pe grafuri dinamice, care dureaza de peste 20 de ani si nu pare sa se apropie de sfarsit.

In aceasta prezentare, nu vom presupune cunostiinte anterioare despre grafuri dinamice, si vom incepe cu o introducere a domeniului. Apoi ne vom concentra pe cateva rezultate recente, si vom discuta multitudinea de probleme care raman inca nerezolvate.