**First,**I was struck by the existence of prior publications on Arxiv. It is no longer exciting to look at lists of papers accepted at a conference: that's not where we learn about new results, but on Arxiv. I knew that, but this brought it home for me: conferences no longer serve the purpose of quickly communicating the latest research results. That was a major service they were doing, perhaps

*the*main one, and that is no longer the case.

Then, why bother look at such a list at all? Because, in areas outside my own small subarea, I don't follow and can't judge what's appearing on Arxiv, so the conference committees provide a useful filter. Why do I care what happens outside my own small subarea? Truly, I do not care very much, but if a big result comes out, I would like to hear about it. Why? So that I don't sound stupid at parties when people ask me about it; and because of some guilty feeling that I ought to be broader, even if I don't really feel like it. In addition, I am always interested if some research happens that might provide good teaching material. Finally, there is a little bit of curiosity: a good talk given by a good speaker on a good topic can be enjoyable even if it's not my area. (Then, it does not even have to be Theory, and in fact, not even Computer Science.)

Those reasons suggest that I do not need to look at lists of accepted papers other than STOC and FOCS, and that I would benefit from those lists more if they were even more selective. I do not want STOC and FOCS to be more selective, but I personally might appreciate it if they were a two-tier conference.

**Second,**I have recently criticized Oded Goldreich's latest essay on Luca Trevisan's blog, but looking at the abstracts of papers accepted at STACS, I could not but recognize the turns of phrase that he lamented. Consider, for example, the paper I mentioned yesterday. Here is the full abstract:

*The Travelling Salesman Problem is one the most fundamental and most studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with approximation factor of 3/2, even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only 4/3. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al., and then by Momke and Svensson. In this paper, we provide an improved analysis for the approach introduced by Momke and Svensson yielding a bound of 13/9 on the approximation factor, as well as a bound of 19/12+epsilon for any epsilon>0 for a more general Travelling Salesman Path Problem in graphic metrics.*

Before I read his essay, I would not have noticed anything special about that abstract. But now, I can see the choice of arguments. Except for the first sentence of the abstract, everything else reads like a list of Olympic race athletic records - an empty race for ever-better approximation factors, with no concern for the underlying structure. The approximation factor has become, not just a (key) indication of the understanding of the problem, but a goal in itself. As I read that, I was a little bit frustrated: I wanted a hint of

*how*the author got that improvement to an important result! What did they learn about the problem, that Moemke and Svensson did not know?

Then I remembered Goldreich's essay.

Strike one for

**Update:**Just to make it clearer. I like the result, I think it's worthwhile, I am interested, I would have been happy to do that research and be an author of that paper. My only quibble is with the style of the abstract.

There is place for all types of research. Improving an approximation ratio is one concrete way for some one to understand previous work on the problem. Senior researchers seem to forget some times that students and younger researchers have to publish what they can to get a degree, a job etc. Also, research progress does not happen simply by thinking big thoughts - people play around with ideas and along the way some times we get lucky.

ReplyDeleteDon't get me wrong, Chandra, I am interested in that paper, and it is definitely worthwhile! In fact I would have been happy to be an author of this paper. Doing it "right" has value, for an important problem and advance! Moemke and Svensson made an important advance, but they didn't do that part quite right; this paper does it right: that's valuable.

ReplyDeleteI'm sorry that didn't come across in my post.

Rather, it's just the style of the abstract that didn't convey that but only the "winning another battle in the war of constants". I only took issue (slightly) with the style, not the result.

Claire,

ReplyDeleteI guess I don't see whether I should interpret the abstract as being instrumental or intellectual in Oded's sense. I might guess he'd say it was instrumental, while I'd call it intellectual, since it seems to me the only implicit motivation is "this is an intellectually interesting problem".

But really, I think competitive analysis is an odd case all its own.

http://mybiasedcoin.blogspot.com/2008/02/conference-reviewing-another-rant-on.html

Whoops. Just realized I pointed to a competitive analysis blog post, when this is an approximation algorithm. The comments (as well as the post), though, tie into the same issues. Apologies.

ReplyDeleteI think everyone is actually in agreement: we don't like the "battle of constants" style of presentation of results.

ReplyDeleteNo, Claire, I disagree. I'm happy with people improving the constants, and I think that as a general rule important, and well worth announcing in an abstract. (See the current debate on Scott Aaronson's blog on the matrix multiplication result...) It just helps if the constants mean something. In this case, you appear to want the new constant to be associated with a new insight or technique that you don't think is being expressed in the abstract.

ReplyDeleteSometimes the constants themselves have meaning: Beating 3/2, even if it was by a tiny 10^{-6} told you that it had to be doing something really new, as in the Gharan, Saberi, Singh paper. The authors would not have needed to explain why this had to use really new ideas. Momke and Svensson's algorithm beats this by a lot but would not have been so interesting if it had not introduced new ideas.

ReplyDeleteOne of the best student papers from FOCS by Hertli gave a new best exponential upper bound for 3-SAT of the form something like 1.30704^n which improves the best constant in the base from 1.32065 and does this in a memorable way. (Though unlike 3/2, I would have had little idea whether 1.30704 was an improvement, especially since some of these results are stated using the log_2 of the base.) The title of the paper is "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General". The title tells you that something interesting is going on (if you know what PPSZ is) but the abstract and intro sure sound as though they would score as "instrumental". I am not sure how one would write the paper differently in these sections.

To me, the issue with this abstract is not whether it is "instrumental" or "intellectual"; it is the blatant marketing going on. Do we really need to be told the TSP is "the most fundamental" and "the most studied" problem?. Does it help the reader to know that "for more than 30 years" there was one bound, while "significant progress" was recently made for an "important" special case? What would be wrong with the following abstract?

ReplyDeleteIn this paper, we provide an improved analysis for the approach to approximating TSP that was introduced by Momke and Svensson, yielding a bound of 13/9 on the approximation factor. Our techniques also give a bound of 19/12+epsilon for any epsilon>0 for a more general Travelling Salesman Path Problem in graph metrics.Anonymous: a little bit of marketing is not bad. For the outsider, what you wrote sounds pretty flat. Only the expert can realize that there is something interesting hidden behind the bland statement. Trying to convey the excitement is a good thing... but it's hard to do it without sounding obnoxious.

ReplyDeleteI guess I don't see whether I should interpret the abstract as being instrumental or intellectual in Oded's sense. I might guess he'd say it was instrumental, while I'd call it intellectual, since it seems to me the only implicit motivation is "this is an intellectually interesting problem".

ReplyDeleteI never consider arxiv publications in my researches. But I was hoping to get some info about them and what benefits I can have from them.

ReplyDelete