I'm currently going through papers for NSDI, and the PC chairs had to send out a post saying how the papers where they are co-authors would be specially handled. NSDI not only allows PC members to submit papers, but the chairs as well!
In the theory community, we generally don't do this. PC members can't submit papers, apparently to avoid any conflict of interest. This is, from what I've seen, unusual, even for CS, which is already unusual in the competitiveness and importance of conferences. Most networking conferences, for instance, allow PC members to submit.
Does conflict of interest really exist in these situations? I don't think so; generally, from what I've seen, it gets handled, and handled appropriately. People on the PC realize it's a competitive process, and understand when their papers aren't accepted. Often when PC members can contribute papers the process is double-blind, so nobody "knows" the PC-authored papers. While I understand allowing PC-authored papers is a risk, I don't think it's much of one. As a comparison point, theory conferences almost never use double-blind reviewing, and I think just the name of a "prestige author" on the paper has a significant effect on the odds of acceptance.
What's the upside? The biggest is that it makes it easier to have larger PCs. I have 20 papers to read for NSDI. I can't remember the last time I had less than 40 papers to review as a PC member for a significant theory conference.
Showing posts with label reviews. Show all posts
Showing posts with label reviews. Show all posts
Thursday, October 23, 2008
Tuesday, July 22, 2008
A Reviewing Story
I'm reminded by some current goings-on about "unusual" reviews, especially one of my worst reviewing experiences ever. I'm sure most everyone has stories of some really painful, inexplicable reviews -- it's like our version of "bad beat" stories in poker -- so here's one of mine.
I had been part of a project that was looking at human-guided search techniques, and specifically we had done a lot of work on 2-D strip-packing, a common problem looked at in the OR and occasionally in the CS literature. Basically, our paper introduced what we would later generalize to Bubblesearch for this problem, and demonstrated how user interaction could lead to even better performance.
We submitted it to a journal-that-will-remain-nameless that claimed it was at the intersection of OR and CS. This seemed a fit to me. This is a standard OR problem; heuristic approaches for it have certainly appeared regularly in other OR journals. We had a very CS-oriented approach, using greedy-based heuristics, and fairly nascent techniques from the interface of AI and user interfaces. We wanted it in front of the OR audience, where human-interaction optimization systems would have been a fairly novel and potentially useful idea.
The reviewers didn't go for it (even after we revised it to answer their complaints). Clearly the human-interaction stuff was a bit beyond what they were able to cope with; if that had really been the main stated objection -- "this is really too AI/UI-ish for us to cope with," then I could have been disappointed by their lack of desire to expand their worldview and moved on. But one reviewer seemed to clearly to think we didn't properly cite and compare results with what I imagine was his own work (which included a paper that was at best tangentially related, and a paper that was apparently under review at another journal and was not publicly available in any format when we wrote ours). Another reviewer simply said that the readers of the journal wouldn't be interested. This is his summary of what we did:
"You look at a simple and natural modification of pretty much the first packing that comes to mind, an idea that could be described over the phone in two minutes, assuming no previous knowledge. Beyond that, you run a bunch of experiments and find out that you get improvements over some metaheuristic." [My note: that "some metaheurisitc" was the one giving the best published results for the problem at the time.]
Yes, that's right, all we did was introduce a painfully simple heuristic -- that hadn't appeared in the literature before, anywhere -- for a well-known, well-studied standard problem, and run experiments showing it beat the best known results on a variety of benchmark instances. I could see why that wouldn't be considered interesting to readers at the OR/CS intersection. Sigh. It's one thing when a reviewer doesn't get your work. It's another when a reviewer gets your work, seems to admit that it's quite good -- at least I view simplicity combined with performance that beats several papers worth of more complicated previous work a plus -- and just says, "But that's not interesting." How do you argue with that?**
I've shied away from the OR community since then. Being fed up at that point, we sent the paper to the Journal of Experimental Algorithmics, where I felt we'd have fewer problems, even if it wasn't exactly the target audience. If you want to read the paper and decide for yourself if the original reviews were warranted, you can find a copy here. (New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing.)
**I admit, I have had to give reviews like that for conference papers -- where the review ends up being, "Sure, I think this is good, you should publish it somewhere, but I'm afraid it's just not in the top x% of the papers I'm seeing and we're space limited for the conference." I hate writing such reviews, but at least I don't make up reasons why the paper isn't good...
I had been part of a project that was looking at human-guided search techniques, and specifically we had done a lot of work on 2-D strip-packing, a common problem looked at in the OR and occasionally in the CS literature. Basically, our paper introduced what we would later generalize to Bubblesearch for this problem, and demonstrated how user interaction could lead to even better performance.
We submitted it to a journal-that-will-remain-nameless that claimed it was at the intersection of OR and CS. This seemed a fit to me. This is a standard OR problem; heuristic approaches for it have certainly appeared regularly in other OR journals. We had a very CS-oriented approach, using greedy-based heuristics, and fairly nascent techniques from the interface of AI and user interfaces. We wanted it in front of the OR audience, where human-interaction optimization systems would have been a fairly novel and potentially useful idea.
The reviewers didn't go for it (even after we revised it to answer their complaints). Clearly the human-interaction stuff was a bit beyond what they were able to cope with; if that had really been the main stated objection -- "this is really too AI/UI-ish for us to cope with," then I could have been disappointed by their lack of desire to expand their worldview and moved on. But one reviewer seemed to clearly to think we didn't properly cite and compare results with what I imagine was his own work (which included a paper that was at best tangentially related, and a paper that was apparently under review at another journal and was not publicly available in any format when we wrote ours). Another reviewer simply said that the readers of the journal wouldn't be interested. This is his summary of what we did:
"You look at a simple and natural modification of pretty much the first packing that comes to mind, an idea that could be described over the phone in two minutes, assuming no previous knowledge. Beyond that, you run a bunch of experiments and find out that you get improvements over some metaheuristic." [My note: that "some metaheurisitc" was the one giving the best published results for the problem at the time.]
Yes, that's right, all we did was introduce a painfully simple heuristic -- that hadn't appeared in the literature before, anywhere -- for a well-known, well-studied standard problem, and run experiments showing it beat the best known results on a variety of benchmark instances. I could see why that wouldn't be considered interesting to readers at the OR/CS intersection. Sigh. It's one thing when a reviewer doesn't get your work. It's another when a reviewer gets your work, seems to admit that it's quite good -- at least I view simplicity combined with performance that beats several papers worth of more complicated previous work a plus -- and just says, "But that's not interesting." How do you argue with that?**
I've shied away from the OR community since then. Being fed up at that point, we sent the paper to the Journal of Experimental Algorithmics, where I felt we'd have fewer problems, even if it wasn't exactly the target audience. If you want to read the paper and decide for yourself if the original reviews were warranted, you can find a copy here. (New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing.)
**I admit, I have had to give reviews like that for conference papers -- where the review ends up being, "Sure, I think this is good, you should publish it somewhere, but I'm afraid it's just not in the top x% of the papers I'm seeing and we're space limited for the conference." I hate writing such reviews, but at least I don't make up reasons why the paper isn't good...
Monday, June 30, 2008
Strange Transactions on Information Theory Policies
The journal where I've published the most now is the IEEE Transactions on Information Theory. (Probably because when I write any journal article in information theory, I send it there, while my other work is more scattered.) So I hope it's clear that, as a journal, I hold it in high regard. That being said, they have some strange policies that I just don't understand. (If you're not familiar with the journal and want to check what I'm saying, their submission guidelines are here.)
First and foremost, they have a distinction between "regular papers" and "correspondence". As they briefly make unclear, "a correspondence item will have one point to make briefly and without adornment, whereas a regular paper will be a more well-rounded treatment of a problem area." In the old days, as far as I can tell, this distinction didn't matter much, and roughly the distinction boiled down to length -- for me, long papers were regular papers, shorter papers were correspondence. Perhaps in the IT community there was more prestige for a regular paper, but I've never been aware of it -- at least in my mind citation count would give a better idea of a paper's importance than its nominal type -- and never cared.
This strangeness didn't become important until recently, when to deal with the apparent problem that the Transactions was becoming too big and thereby using too much paper [yes, I know this shouldn't be a problem, but they still send out lots of paper copies], they limited correspondence items to 5 journal pages.
This, to me, is just strange. First, I dislike the idea of page limits in general for journals. The journal is supposed to be the "permanent record" of a scientific result. If it takes 50 pages to present the result, then that's what it takes. A journal certainly has a right (indeed, perhaps a duty) to have authors properly edit a work so that there's not a gross amount of wasted verbiage, but to set a priori page limits, in my mind, goes against the purported purpose of journal publication.
Second, I don't see how this page limit jibes with this (already strange) regular paper/correspondence distinction. Sometimes, presenting a single point briefly takes more than 5 pages. (Arguably, it often takes this long, if one wants to do a suitable job presenting previous work, or substantial mathematical setup must be done.)
As an example, I submitted a paper to ToIT. I thought it was clearly a correspondence, according to their definition, since it really covered a single thematic issue. Given the policy, I wasted at least a day cutting things from my version to make it a (just over) 5 page submission version. (I had tables and a picture -- it really was a hard exercise to cut that last page.)
The reviews came back, and most of the complaints were questions of the form, "Why don't you talk about Z?", where in fact my discussion of Z was something I took out to get things down to 5 pages. (Duh.) The editor asked the editor-in-chief -- no exceptions to the 5 page rule.
So the editor, smartly, decided that I had a 6-page regular paper. While I appreciated the solution, the whole thing just highlighted the silliness of the policy, and perhaps the strangeness in distinguishing "regular papers" and "correspondence" in the first place.
Another policy I object to is their decision not to publish already-published conference articles unless there is "substantially new" material. (This is not spelled out, but I have been told the rough figure is "30% of the article must be new", whatever that means.) Again, in my mind, this goes against the purported purpose of a journal as the final record of a research result. Conference papers are, in my mind, dramatically more likely to be wrong, and at the very least have generally had little feedback in the reviewing process. A journal is supposed to provide more in terms of reviewing; if a conference paper and journal paper ended up identical, I'd have no problem with it -- and I'd congratulate the author on writing such a solid conference version (assuming I didn't question the reviewing practices of the journal).
I can understand this policy in the context of copyright. An IEEE journal can't (re-)publish something another organization has the copyright to, and an author should understand this. But when the paper was in an IEEE conference -- what's the problem?
These two policies interact in a very strange way in the context of the IEEE International Symposium on Information Theory (ISIT) -- the big IT conference. ISIT papers are -- get this -- 5 pages. One might naturally hope that ISIT papers could be turned right over into Transactions correspondences -- and get the benefit of more complete reviewing and editing for that "final version". But not, it seems, under the current policy that the journal version must have something "new" over the conference version. But I can't add anything new to my 5 page conference version without going over that arbitrary 5 page correspondence limit. Am I the only one that sees something wrong with that picture? (And yes, I have ISIT papers that I won't bother submitting to ToIT, because they're really correspondences that should/would be 6-7 pages once I add that 30% new stuff in.) If they're going to not publish things from conferences, even IEEE conferences, then having a 5 page ISIT limit and a 5 page correspondence limit is, in my mind, just strange.
First and foremost, they have a distinction between "regular papers" and "correspondence". As they briefly make unclear, "a correspondence item will have one point to make briefly and without adornment, whereas a regular paper will be a more well-rounded treatment of a problem area." In the old days, as far as I can tell, this distinction didn't matter much, and roughly the distinction boiled down to length -- for me, long papers were regular papers, shorter papers were correspondence. Perhaps in the IT community there was more prestige for a regular paper, but I've never been aware of it -- at least in my mind citation count would give a better idea of a paper's importance than its nominal type -- and never cared.
This strangeness didn't become important until recently, when to deal with the apparent problem that the Transactions was becoming too big and thereby using too much paper [yes, I know this shouldn't be a problem, but they still send out lots of paper copies], they limited correspondence items to 5 journal pages.
This, to me, is just strange. First, I dislike the idea of page limits in general for journals. The journal is supposed to be the "permanent record" of a scientific result. If it takes 50 pages to present the result, then that's what it takes. A journal certainly has a right (indeed, perhaps a duty) to have authors properly edit a work so that there's not a gross amount of wasted verbiage, but to set a priori page limits, in my mind, goes against the purported purpose of journal publication.
Second, I don't see how this page limit jibes with this (already strange) regular paper/correspondence distinction. Sometimes, presenting a single point briefly takes more than 5 pages. (Arguably, it often takes this long, if one wants to do a suitable job presenting previous work, or substantial mathematical setup must be done.)
As an example, I submitted a paper to ToIT. I thought it was clearly a correspondence, according to their definition, since it really covered a single thematic issue. Given the policy, I wasted at least a day cutting things from my version to make it a (just over) 5 page submission version. (I had tables and a picture -- it really was a hard exercise to cut that last page.)
The reviews came back, and most of the complaints were questions of the form, "Why don't you talk about Z?", where in fact my discussion of Z was something I took out to get things down to 5 pages. (Duh.) The editor asked the editor-in-chief -- no exceptions to the 5 page rule.
So the editor, smartly, decided that I had a 6-page regular paper. While I appreciated the solution, the whole thing just highlighted the silliness of the policy, and perhaps the strangeness in distinguishing "regular papers" and "correspondence" in the first place.
Another policy I object to is their decision not to publish already-published conference articles unless there is "substantially new" material. (This is not spelled out, but I have been told the rough figure is "30% of the article must be new", whatever that means.) Again, in my mind, this goes against the purported purpose of a journal as the final record of a research result. Conference papers are, in my mind, dramatically more likely to be wrong, and at the very least have generally had little feedback in the reviewing process. A journal is supposed to provide more in terms of reviewing; if a conference paper and journal paper ended up identical, I'd have no problem with it -- and I'd congratulate the author on writing such a solid conference version (assuming I didn't question the reviewing practices of the journal).
I can understand this policy in the context of copyright. An IEEE journal can't (re-)publish something another organization has the copyright to, and an author should understand this. But when the paper was in an IEEE conference -- what's the problem?
These two policies interact in a very strange way in the context of the IEEE International Symposium on Information Theory (ISIT) -- the big IT conference. ISIT papers are -- get this -- 5 pages. One might naturally hope that ISIT papers could be turned right over into Transactions correspondences -- and get the benefit of more complete reviewing and editing for that "final version". But not, it seems, under the current policy that the journal version must have something "new" over the conference version. But I can't add anything new to my 5 page conference version without going over that arbitrary 5 page correspondence limit. Am I the only one that sees something wrong with that picture? (And yes, I have ISIT papers that I won't bother submitting to ToIT, because they're really correspondences that should/would be 6-7 pages once I add that 30% new stuff in.) If they're going to not publish things from conferences, even IEEE conferences, then having a 5 page ISIT limit and a 5 page correspondence limit is, in my mind, just strange.
Tuesday, June 10, 2008
Scientific Citations
A comment over at Lance's blog got me thinking about citations. To summarize, some anonymous commenter said that if a paper wasn't easily available online (specifically, "not available for free online (or through my acm portal subscription)") , they won't read or cite it, and then another commenter pointed out that it was the author's responsibility to acknowledge relevant work, give proper credit, and avoid duplicating previous work.
I certainly agree in spirit with the second comment, but I wonder, exactly, what are our responsibilities as authors? How much hunting, exactly, am I as an author expected to do to find relevant work? This is certainly an issue I've faced in my own work. For example, I've had the case where there may be a related article in an old Russian mathematics journal -- an article pops up in my search of related keywords and either the title or abstract seems potentially relevant, but I can't really tell without getting the article. So far, I've managed -- the blessings of always being near the Berkeley, Stanford, Harvard, or MIT libraries -- but it has sometimes been a non-trivial effort to track it down. In the old days, that library time was more or less expected. What expectations should there be in terms of tracking down old paper copies? What expectations should there be in terms of what an author is required to "spend" to get copies of possibly related work? I do think there is a reasonable argument that can be made that if your paper isn't freely available, an author can't necessarily be expected to cite it.
And of course I wouldn't have even faced the tracking problem except that I try to be diligent in my searches for relevant work. Working across areas, I've often found I have to spend some time guessing and doing some random walks to find out what people in another area call the concept I'm thinking about just to find the relevant papers. How much searching in Google/Google Scholar/your tool of choice should be expected of us? (I'm thinking here of the really annoying reviews I sometimes get of the form, "You should have cited this paper, I'm going to suggest rejecting your paper." That's inane. Perhaps I should have cited the paper, in which case, you should suggest that I cite the paper; that's what reviews are for.)
After all this, there's still the question of what should be cited. Science rules seem much "looser" than what I've seen in literature, history, etc. I'd never think of citing Karp or Garey and Johnson if I was showing a standard NP-completeness result (unless there was a very specific reason to do so) because it's now considered common knowledge. I think in many humanities fields that would be considered improper. Perhaps standards for various fields should be codified -- if only so that people in one field can easily understand the practices in another.
I certainly agree in spirit with the second comment, but I wonder, exactly, what are our responsibilities as authors? How much hunting, exactly, am I as an author expected to do to find relevant work? This is certainly an issue I've faced in my own work. For example, I've had the case where there may be a related article in an old Russian mathematics journal -- an article pops up in my search of related keywords and either the title or abstract seems potentially relevant, but I can't really tell without getting the article. So far, I've managed -- the blessings of always being near the Berkeley, Stanford, Harvard, or MIT libraries -- but it has sometimes been a non-trivial effort to track it down. In the old days, that library time was more or less expected. What expectations should there be in terms of tracking down old paper copies? What expectations should there be in terms of what an author is required to "spend" to get copies of possibly related work? I do think there is a reasonable argument that can be made that if your paper isn't freely available, an author can't necessarily be expected to cite it.
And of course I wouldn't have even faced the tracking problem except that I try to be diligent in my searches for relevant work. Working across areas, I've often found I have to spend some time guessing and doing some random walks to find out what people in another area call the concept I'm thinking about just to find the relevant papers. How much searching in Google/Google Scholar/your tool of choice should be expected of us? (I'm thinking here of the really annoying reviews I sometimes get of the form, "You should have cited this paper, I'm going to suggest rejecting your paper." That's inane. Perhaps I should have cited the paper, in which case, you should suggest that I cite the paper; that's what reviews are for.)
After all this, there's still the question of what should be cited. Science rules seem much "looser" than what I've seen in literature, history, etc. I'd never think of citing Karp or Garey and Johnson if I was showing a standard NP-completeness result (unless there was a very specific reason to do so) because it's now considered common knowledge. I think in many humanities fields that would be considered improper. Perhaps standards for various fields should be codified -- if only so that people in one field can easily understand the practices in another.
Tuesday, April 01, 2008
Jennifer Rexford's take on "Practical Theory"
Jennifer Rexford, who I've mentioned before is a networking person who appreciates theory, gave me a rumor that she'll be giving a talk at STOC on "networking questions relevant to the theoretical CS community." I don't see the program up yet, but I hope it's true. She's a great speaker, with excellent perspective. Kudos to those who thought to invite her!!!
She also pointed me to an editorial she wrote on her ten favorite "practical theory" papers. Naturally, I enjoyed reading her perspective. Particularly since her perspective included my name (flattery, indeed, will you get you everywhere-- or at least on my blog).
I think, however, her editorial offers several lessons. Here's my top two. First, her notion of a theory paper is a little different than ours. Most of the papers are by networking people who think mathematically and theoretically (Varghese, Towsley) or more attuned to what I think of as EE theory. This first lesson is a reaffirmation of my long-standing notion that the FOCS/STOC view of theory is, in many respects, rather limited, especially to our peers outside of theory. I think a second related lesson goes to the importance of theory people getting out there and making their work more accessible to non-theorists. In my case, that has meant writing survey articles, giving talks for general audiences and not just theorists, and going to networking conferences to talk about my work. I'm sure there's plenty of other "mainstream theory" work that Jennifer and others from networking would greatly appreciate -- if only we as a community did a bit better job of letting them know about it.
She also pointed me to an editorial she wrote on her ten favorite "practical theory" papers. Naturally, I enjoyed reading her perspective. Particularly since her perspective included my name (flattery, indeed, will you get you everywhere-- or at least on my blog).
I think, however, her editorial offers several lessons. Here's my top two. First, her notion of a theory paper is a little different than ours. Most of the papers are by networking people who think mathematically and theoretically (Varghese, Towsley) or more attuned to what I think of as EE theory. This first lesson is a reaffirmation of my long-standing notion that the FOCS/STOC view of theory is, in many respects, rather limited, especially to our peers outside of theory. I think a second related lesson goes to the importance of theory people getting out there and making their work more accessible to non-theorists. In my case, that has meant writing survey articles, giving talks for general audiences and not just theorists, and going to networking conferences to talk about my work. I'm sure there's plenty of other "mainstream theory" work that Jennifer and others from networking would greatly appreciate -- if only we as a community did a bit better job of letting them know about it.
Saturday, March 15, 2008
Error-Correction Mechanisms for Publications
I very much like the conference-based publication system of computer science. But an obvious problem with the system -- which mathematicians sometimes throw back in the face of CS theory researchers -- is that this system leads to buggy results getting published and accepted by the community. (In my last post, I talked about the headaches this issue can cause PC members.)
This problem could be ameliorated if as a community we had some standard ways of reporting or dealing with such errors. But I don't think we really do. Occasionally an author will self-report an error or fix something for a journal version, but I imagine errors slip through more often than we'd care to think about. Perhaps it isn't really a problem; for big, important papers, bugs will be found and knowledge of them disseminated. But for smaller papers (which, let's face it, is most of what actually gets written -- even in the major conferences), there doesn't seem to be a process -- in fact, even trying to suggest that there's a bug in someone's work can get your own paper killed.
Yes, I'm unhappy to report, this happened to me. Once, on a paper, a student found a bug in some previous related work, and thought it important to mention in the conference submission to deal with possible questions about how our work related to this other paper. [Since he's job-hunting, I feel I should say this was NOT Adam.] After going back and forth, I agreed that we could in a footnote mention that there appeared to be an error that we were discussing with the author. (The author took a while to admit there was an error, and in fact the student helped suggest a fix.) The PC sent back nasty reviews, with one even suggesting that our action was unprofessional. I, obviously, disagree. This was a submission, ostensibly confidential, not for publication (the PC could ask us to remove the footnote if they objected). We were in contact with the author and trying to clarify and fix the bug we found. How the heck else were we supposed to let the committee know what was going on, if they felt it important? If they felt it wasn't important, it was just a footnote they were welcome to skip.
This attitude, I think, stems from the fact that, on the whole, we're a very pleasant, non-confrontational area of science. Fights in CS theory are rare; most people get along (professionally) quite well. From what I've seen, with rare exception, we're much less confrontational than other sciences. So somehow mentioning out loud that someone might have made a mistake is not considered good form. Again, I may be wrong, but other sciences seem less sanguine.
Of course, the underlying problem in this incident, and others I've seen as a PC member and in other contexts, is that we don't have an error-correction mechanism that allows one to report bugs or suspected bugs in published work. Perhaps we're better off without it -- maybe it would just take up time and provide little value. But I've never heard it even come up as an issue to be thought about and discussed by the community. Perhaps it should.
This problem could be ameliorated if as a community we had some standard ways of reporting or dealing with such errors. But I don't think we really do. Occasionally an author will self-report an error or fix something for a journal version, but I imagine errors slip through more often than we'd care to think about. Perhaps it isn't really a problem; for big, important papers, bugs will be found and knowledge of them disseminated. But for smaller papers (which, let's face it, is most of what actually gets written -- even in the major conferences), there doesn't seem to be a process -- in fact, even trying to suggest that there's a bug in someone's work can get your own paper killed.
Yes, I'm unhappy to report, this happened to me. Once, on a paper, a student found a bug in some previous related work, and thought it important to mention in the conference submission to deal with possible questions about how our work related to this other paper. [Since he's job-hunting, I feel I should say this was NOT Adam.] After going back and forth, I agreed that we could in a footnote mention that there appeared to be an error that we were discussing with the author. (The author took a while to admit there was an error, and in fact the student helped suggest a fix.) The PC sent back nasty reviews, with one even suggesting that our action was unprofessional. I, obviously, disagree. This was a submission, ostensibly confidential, not for publication (the PC could ask us to remove the footnote if they objected). We were in contact with the author and trying to clarify and fix the bug we found. How the heck else were we supposed to let the committee know what was going on, if they felt it important? If they felt it wasn't important, it was just a footnote they were welcome to skip.
This attitude, I think, stems from the fact that, on the whole, we're a very pleasant, non-confrontational area of science. Fights in CS theory are rare; most people get along (professionally) quite well. From what I've seen, with rare exception, we're much less confrontational than other sciences. So somehow mentioning out loud that someone might have made a mistake is not considered good form. Again, I may be wrong, but other sciences seem less sanguine.
Of course, the underlying problem in this incident, and others I've seen as a PC member and in other contexts, is that we don't have an error-correction mechanism that allows one to report bugs or suspected bugs in published work. Perhaps we're better off without it -- maybe it would just take up time and provide little value. But I've never heard it even come up as an issue to be thought about and discussed by the community. Perhaps it should.
Thursday, March 13, 2008
Conferences and Correctness
A post by Mihai Patrascu brought up the difficult issue of how to deal with papers that may or may not be correct when on a program committee. This is, clearly, a difficult question, and can lead to tremendous difficulties, as it is often not a simple task to determine correctness.
One approach is when an issue arises to inform the author(s) and ask them to clear up the issue. I recommend this, but it is not always functional; there may be disagreements between the author and the reviewers, and there is usually a limited amount of time to settle the problem.
Also, this seems to set up an onus on the author that may be unfair: you must convince us (outside what you've already written) that your proofs are correct. Now, that might not sound like an unfair onus, but for a difficult proof it may be very challenging, particularly since initially all that's been asked for (in most conferences) is a 10 page abstract and not the "final" version. Moreover, it's unfair because it's not something you're really asking of all the other authors. Sure, nominally you are, but papers with bugs get through often enough. Sometimes we make mistakes, and arguably there is some unfairness in a policy that insists that suspicious paper X must now be proven until all reviewers are fully satisfied while papers that didn't raise suspicions pass right on through.
As I've mentioned, I think the main job of the PC is to prioritize what papers get in a conference, and a secondary job is to give feedback to the authors. As part of that job, naturally, we want to throw out papers that are wrong and let the authors know about mistakes. But my argument is that conferences (and PCs) are not designed to accurately tell if papers are completely correct. If they were, I wouldn't have 45 papers to consider in a bit over a month, and I wouldn't be given papers on topics like quantum computing to judge. Ensuring correctness is nominally what journals are for, and that's why (in general) journal articles can take more time to review, and why one seeks experts for reviewing.
I'm not sure what a good solution is, and I'm not advocating blindly giving benefit of the doubt to papers that appear wrong. But there should be a high-level understanding that the conference procedure is inherently noisy. Mistaken proofs might be published. Perhaps the problem we should turn our attention to is how, as a community, we handle these errors, including arranging for such errors to be corrected or noted (by the authors or otherwise) in an appropriate fashion.
One approach is when an issue arises to inform the author(s) and ask them to clear up the issue. I recommend this, but it is not always functional; there may be disagreements between the author and the reviewers, and there is usually a limited amount of time to settle the problem.
Also, this seems to set up an onus on the author that may be unfair: you must convince us (outside what you've already written) that your proofs are correct. Now, that might not sound like an unfair onus, but for a difficult proof it may be very challenging, particularly since initially all that's been asked for (in most conferences) is a 10 page abstract and not the "final" version. Moreover, it's unfair because it's not something you're really asking of all the other authors. Sure, nominally you are, but papers with bugs get through often enough. Sometimes we make mistakes, and arguably there is some unfairness in a policy that insists that suspicious paper X must now be proven until all reviewers are fully satisfied while papers that didn't raise suspicions pass right on through.
As I've mentioned, I think the main job of the PC is to prioritize what papers get in a conference, and a secondary job is to give feedback to the authors. As part of that job, naturally, we want to throw out papers that are wrong and let the authors know about mistakes. But my argument is that conferences (and PCs) are not designed to accurately tell if papers are completely correct. If they were, I wouldn't have 45 papers to consider in a bit over a month, and I wouldn't be given papers on topics like quantum computing to judge. Ensuring correctness is nominally what journals are for, and that's why (in general) journal articles can take more time to review, and why one seeks experts for reviewing.
I'm not sure what a good solution is, and I'm not advocating blindly giving benefit of the doubt to papers that appear wrong. But there should be a high-level understanding that the conference procedure is inherently noisy. Mistaken proofs might be published. Perhaps the problem we should turn our attention to is how, as a community, we handle these errors, including arranging for such errors to be corrected or noted (by the authors or otherwise) in an appropriate fashion.
Saturday, March 01, 2008
Another Rant from Conference Reviewing : Algorithms and Evaluation
After my first conference rant on competitive analysis (based on my current stints on the SPAA and ICALP committees), I feel it's only fair to spread the love and rant a bit on my fellow algorithmists.
I simply claim the following : if you are presenting an algorithm with the claim that it might be useful in practice, you should aim to include at least a short experimental section showing that you've implemented the algorithm and that it/how it behaves.
Here's why:
1) If your suggestion is it's potentially going to be useful in practice, and it's your algorithm, it's incumbent on you to provide some evidence for this statement. An implementation is the best evidence. I don't expect pages of simulation results examining corner cases (although, if there's space, that's certainly nice); but a couple of paragraphs explaining that you implemented it, tested on basic data, and the program actually finished goes a long way.
2) It's not that I don't trust your math. It's just that -- well, no, it is just that I don't trust your math. Maybe you've proven that the algorithm is O(n^2). I'd like to know if in practice it seems to be O(n log n) [even if it's O(n^2) in the worst case -- now you've given an average-case or special-case open problem!]. I'd like to know if there's a hidden constant of 10,000 there that makes it really not practical in its current form. I'd like to see that you didn't make an error and that it doesn't look like Theta(n^3) when you run it. [I've got 46 papers to look over in a month. Make my job easier, your paper's more likely to get in.]
3) Maybe, just maybe, someone who might actually want to implement your algorithm will actually read your paper. A non-theorist. Don't you think they want to see that it seems to actually work before implementing it better themselves? Won't some experiments make talking about your work to non-theorists easier? Help make that connection...
I'm not saying every algorithms paper needs an implementation section. In many cases, "algorithmic" results are really "complexity" results -- we're just showing that something can be done, we don't actually expect anyone to do it, and in this case there's no need for a simulation or experimental results. (Of course, in such cases, I expect the authors to limit their claims of interest/utility in practice.) In some cases, space won't permit a reasonable evaluation of the algorithm -- but do plan on it for the journal version. In some cases, the coding and evaluation of the algorithm are so interesting it merits an entirely separate paper!
But I'm amazed at how few algorithms papers provide any actual experimental results (unless they're appearing in a networking/database/other systems conference, where it's more understood that results are also expected). I've actually submitted theory papers to theory conferences with experimental sections and had reviewers urge them to be taken out, which I find mystifying (and I ignore).
And yes, if I'm reviewing your paper, and you don't have any numbers where I think you should, I'm probably mentally (and numerically) docking your paper score....
I simply claim the following : if you are presenting an algorithm with the claim that it might be useful in practice, you should aim to include at least a short experimental section showing that you've implemented the algorithm and that it/how it behaves.
Here's why:
1) If your suggestion is it's potentially going to be useful in practice, and it's your algorithm, it's incumbent on you to provide some evidence for this statement. An implementation is the best evidence. I don't expect pages of simulation results examining corner cases (although, if there's space, that's certainly nice); but a couple of paragraphs explaining that you implemented it, tested on basic data, and the program actually finished goes a long way.
2) It's not that I don't trust your math. It's just that -- well, no, it is just that I don't trust your math. Maybe you've proven that the algorithm is O(n^2). I'd like to know if in practice it seems to be O(n log n) [even if it's O(n^2) in the worst case -- now you've given an average-case or special-case open problem!]. I'd like to know if there's a hidden constant of 10,000 there that makes it really not practical in its current form. I'd like to see that you didn't make an error and that it doesn't look like Theta(n^3) when you run it. [I've got 46 papers to look over in a month. Make my job easier, your paper's more likely to get in.]
3) Maybe, just maybe, someone who might actually want to implement your algorithm will actually read your paper. A non-theorist. Don't you think they want to see that it seems to actually work before implementing it better themselves? Won't some experiments make talking about your work to non-theorists easier? Help make that connection...
I'm not saying every algorithms paper needs an implementation section. In many cases, "algorithmic" results are really "complexity" results -- we're just showing that something can be done, we don't actually expect anyone to do it, and in this case there's no need for a simulation or experimental results. (Of course, in such cases, I expect the authors to limit their claims of interest/utility in practice.) In some cases, space won't permit a reasonable evaluation of the algorithm -- but do plan on it for the journal version. In some cases, the coding and evaluation of the algorithm are so interesting it merits an entirely separate paper!
But I'm amazed at how few algorithms papers provide any actual experimental results (unless they're appearing in a networking/database/other systems conference, where it's more understood that results are also expected). I've actually submitted theory papers to theory conferences with experimental sections and had reviewers urge them to be taken out, which I find mystifying (and I ignore).
And yes, if I'm reviewing your paper, and you don't have any numbers where I think you should, I'm probably mentally (and numerically) docking your paper score....
Wednesday, February 20, 2008
Conference Reviewing: Another Rant on Competitive Analysis
Because of an inadequate lack of attention regarding conference deadlines on my part, I find myself currently reading lots of papers while concurrently serving on the SPAA and ICALP Program Committees.
And somehow, this means I'm reading lots of papers with competitive analyses of algorithms. (Both the standard variety, and the more new-fangled but generally similar "price of anarchy" variety.) Looking back on it, I should have simply have told the PC chairs that it might be best to make sure not to assign me any such papers, as I'm not sure it's fair to the authors who get me as a reviewer.
OK, I'm exaggerating. Don't get me wrong; I'm not automatically assigning negative scores to any such paper. Some of these papers I really like. But in general, as I've expressed frequently elsewhere, I'm a skeptic when it comes to competitive analysis. Why exactly should anyone care that you have an algorithm that in the worst case always gets within a factor of 6.5 of the optimal solution possible? Why is that the right way to judge an algorithm? (Never mind the offshoots, like those where you have an algorithm that's competitive if it has twice as much as memory as you allow for the optimal algorithm, and so on...)
In my mind, the problem is that competitive analysis has become such a standard in Theoretical Computer Science that people don't feel the need to bother justifying anywhere in the paper why they should use competitive analysis, when in fact these papers scream for a need for motivation.
Here are some motivations that tend to work for me when reading competitive analysis papers.
1. The resulting problem is just so mathematically interesting that we really have to look at it. (One person I can think of that manages to pull off this motivation with me time and again is Susanne Albers.) Generally, to pull off this motivation, your problem should be simple, clean, and natural; if you start to bog down in details, claiming that you're giving a "more realistic" model of the problem, you've already missed the boat in my mind. (If you really wanted to be realistic, you wouldn't be using competitive analysis...)
2. You are considering the performance of real, existing algorithms. This seems reasonable to me; here's something people actually do (like, say, Shortest Job First scheduling), and you want to gain some insight into its worst-case performance for this notion of worst-case. Many price-of-anarchy results actually correspond to the behavior of reasonable algorithms one might consider in practice, so I admit I often find myself more sympathetic to Price of Anarchy results, which seem more motivated.
3. You are using competitive analysis for an essentially (complexity)-theoretical result.
4. You are using competitive analysis to gain significant insight into the problem (and algorithms for the problem) that could be useful in understanding real performance or designing real algorithms. I think most papers implicitly claim that their paper fits into this last category, just because it obviously doesn't fit into the other three, but usually this isn't explicitly discussed. I think this motivation works best when the problem is inherently very hard.
I'm sure there are other reasonable motivations. But overall I would call for more restraint from the community; not everything should be subjected to competitive analysis, just because it can.
And somehow, this means I'm reading lots of papers with competitive analyses of algorithms. (Both the standard variety, and the more new-fangled but generally similar "price of anarchy" variety.) Looking back on it, I should have simply have told the PC chairs that it might be best to make sure not to assign me any such papers, as I'm not sure it's fair to the authors who get me as a reviewer.
OK, I'm exaggerating. Don't get me wrong; I'm not automatically assigning negative scores to any such paper. Some of these papers I really like. But in general, as I've expressed frequently elsewhere, I'm a skeptic when it comes to competitive analysis. Why exactly should anyone care that you have an algorithm that in the worst case always gets within a factor of 6.5 of the optimal solution possible? Why is that the right way to judge an algorithm? (Never mind the offshoots, like those where you have an algorithm that's competitive if it has twice as much as memory as you allow for the optimal algorithm, and so on...)
In my mind, the problem is that competitive analysis has become such a standard in Theoretical Computer Science that people don't feel the need to bother justifying anywhere in the paper why they should use competitive analysis, when in fact these papers scream for a need for motivation.
Here are some motivations that tend to work for me when reading competitive analysis papers.
1. The resulting problem is just so mathematically interesting that we really have to look at it. (One person I can think of that manages to pull off this motivation with me time and again is Susanne Albers.) Generally, to pull off this motivation, your problem should be simple, clean, and natural; if you start to bog down in details, claiming that you're giving a "more realistic" model of the problem, you've already missed the boat in my mind. (If you really wanted to be realistic, you wouldn't be using competitive analysis...)
2. You are considering the performance of real, existing algorithms. This seems reasonable to me; here's something people actually do (like, say, Shortest Job First scheduling), and you want to gain some insight into its worst-case performance for this notion of worst-case. Many price-of-anarchy results actually correspond to the behavior of reasonable algorithms one might consider in practice, so I admit I often find myself more sympathetic to Price of Anarchy results, which seem more motivated.
3. You are using competitive analysis for an essentially (complexity)-theoretical result.
4. You are using competitive analysis to gain significant insight into the problem (and algorithms for the problem) that could be useful in understanding real performance or designing real algorithms. I think most papers implicitly claim that their paper fits into this last category, just because it obviously doesn't fit into the other three, but usually this isn't explicitly discussed. I think this motivation works best when the problem is inherently very hard.
I'm sure there are other reasonable motivations. But overall I would call for more restraint from the community; not everything should be subjected to competitive analysis, just because it can.
Tuesday, July 31, 2007
The Reviewers' Pledges
The state of journal reviewing in CS and EE journals is generally pretty dismal. It often takes an unforgivably long time to get reviews back, and often reviews offer less in the way the feedback and constructive criticism than one might hope.
Here I'll focus on aspects related to timing. (I'm unconvinced that reviews that take longer to get back are any better in terms of feedback. Often, just the opposite -- the reviewer realizes the paper has been on their desk too long and just writes a quick paragraph to be done with it.) Let me suggest a set of basic pledges -- rules that everyone should follow. Feel free to suggest your own additions....
Here I'll focus on aspects related to timing. (I'm unconvinced that reviews that take longer to get back are any better in terms of feedback. Often, just the opposite -- the reviewer realizes the paper has been on their desk too long and just writes a quick paragraph to be done with it.) Let me suggest a set of basic pledges -- rules that everyone should follow. Feel free to suggest your own additions....
- When asked to review a paper, I will respond as quickly as possible, even if the answer is no.
- I will review at least 1 journal paper for every journal paper I submit. (This does not mean "I will give my graduate students 1 paper to review for every journal paper I submit." Though graduate students should also do reviewing...)
- I will skim through a paper I plan to review within one month of receiving it, so that if it is a clear reject for any reason, or there is an important question that needs to be raised, I can promptly write a short note to the editor (and thereby hopefully avoid a more detailed review).
- I pledge to review papers within six months of receiving them. I acknowledge that six months is an upper bound, not a target deadline.
- I accept that there is reviewing karma, and I should not be surprised if editors pass my papers on to slow reviewers if I am a slow reviewer.
Subscribe to:
Posts (Atom)