Friday, April 20, 2007

Meta Comment on FOCS/STOC comments

The comments on both Vijay's guest post and Lance's post brought out many comments about FOCS/STOC. People seem to have strong feelings and stronger opinions. Here is a list of questions this discussion has raised.
  1. Is the community really driven by these conferences? An Underlying assumption of these discussions has been that someone judges us based on the number of STOC/FOCSs we have. Who is this mysterious someone? Is it our departments? Our Colleges? Ourselves? Granting agencies?
  2. Is it bad that we are so judged?? PRO: Its good to have a central place where you know the good papers are. CON: The rest of the items on this list are about what problems there are in judging quality CON: Some of these papers are never put into proper journal form. CAVEAT: Is the Journal-Refereeing system all that good to decry that it is lacking here?
  3. Other fields do not have high-prestige conferences- why do we and is it a good thing?. Our field moves fast so we want to get results out fast. It is not clear that FOCS/STOC really do this. Using the web and/or Blogs can get the word out. Important new results in theory get around without benefit of conferences. For results just below that threshold its harder to say.
  4. Are the papers mostly good?
  5. Is their a Name-School-bias? Is their a Name-person-bias? Some have suggested anonymous submissions to cure this problem.
  6. Is their an area-bias? There are several questions here: (1) is the list-of-topics on the conference annoucement leaving off important parts of theory? (2) is the committee even obeying the list as is? (3) have some areas just stopped submitting?
  7. Is their a Hot-area-bias?
  8. Is their a mafia that controls which topics gets in?
  9. Is their a bias towards people who can sell themselves better? To people that can write well?
  10. Is their a bias towards making progress on old problems rather than starting work on new problems?
  11. Is their a bias towards novel or hard techniques?
  12. Is it just Random? Aside from the clearly good and clearly bad papers, is it random? Is even determining clearly good and clearly bad also random? One suggestion is to make it pseudo-random by using the NW-type generators. This solves the problem in that since it really is random it is less prestigous and most of the problems on this list go away. Would also save time and effort since you would not need a program committee.
  13. Are there many very good papers that do not get in? It has been suggested that we go to double sessions so that more get in. If the quality of papers has been going up over time this might make sense and would not dilute quality.
  14. Is 10 pages too short for submissions? This was part of Vijay's Video Suggestion. Are figures and diagrams counted for those 10 pages? If they are they shouldn't be.
  15. Are many submissions written at the last minute and hence badly written?
  16. Are many submissions written by the authors taking whatever they have by the deadline and shoving it into a paper?
  17. Since the conference is about all of theory, can any committee do a good job?Vijay was partially addressing this problem by trying to find a way to make their job easier.
  18. Do other conferences have these problems? That is, the more specialized conferences- do they have similar problems? Why or why not?
  19. Do you actually get that much out of the talks? If not then it is still valuable to to go for the people you meet in the hallways?
  20. For all the items above, even if true, are they bad? Some have suggested that bias towards big-names is okay.
Any proposed change in STOC/FOCS (or other conferences) should have the following:
  1. State clearly what problem you are trying to solve. If it is a new problem there may be a bias against it.
  2. Prove that it really is a problem. The proof has to use novel or difficult techniques.
  3. State clearly what your solution is and proof that it works. The proof can be a sketch; however, if you are a big-name or from a big-name-school then people will pay more attention.
  4. Comments to your suggestion must stay on topic. A referees report would never say: `The author showed that 3-colorability can be approximated well; however, the really important problem in this field is set cover, which can be shown to not be approximated by the following.'' But a comment on a blog often says things like: ``Vijay is addressing one problem with STOC/FOCS, but the real problem is ...''

33 comments:

  1. I posted my responses over at the Geomblog.

    ReplyDelete
  2. > ...someone judges us based on the number of STOC/FOCSs we have. Who is this mysterious someone?

    ...and who are these mysterious "we"? I feel "FOCS-measuring" is mostly concentrated on the US territory.

    ReplyDelete
  3. > ...and who are these mysterious "we"? I feel "FOCS-measuring" is mostly concentrated on the US territory.


    I agree.

    ReplyDelete
  4. > ...and who are these mysterious "we"? I feel "FOCS-measuring" is mostly concentrated on the US territory.

    I agree.


    So do I.

    ReplyDelete
  5. Is Israel counted as eropean country?

    ReplyDelete
  6. > Is Israel counted as e(u)ropean country.

    Who said about European countries?

    There are other parts of the world in addition to the US and Europe (at least, this is what the teach at school :) ).

    ReplyDelete
  7. In the Israeli theory community, there is certainly an emphasis on STOC/FOCS papers.
    This is especially crucial in early stages of the career, where fast turnaround is needed to show impact.
    In later stages (tenure and onwards), Israeli universities do expect to see more journal publications than in the US.
    (This is gross generalization, of course, and exceptions happen.)

    More to the topic of this post, what we should be discussing is how to improve journal turnaround time.
    After all, in the other sciences, journals respond much faster (in a time scale similar to our conference reviewing).
    My impression is that we inhereted the very serious reviewing process from Math, but want to publish in the volumes of the Life Sciences.

    ReplyDelete
  8. My impression is that we inhereted the very serious reviewing process from Math, but want to publish in the volumes of the Life Sciences.

    The problem is that the exponent base is too high. We produce too many CS PhD students, who start to publish much earlier than to referee.

    ReplyDelete
  9. Check up the difference between 'their' and 'there'.

    ReplyDelete
  10. Regarding second point on the second list.

    "Prove that it really is a problem. The proof has to use novel or difficult techniques."

    Why do we want the prood to be difficult. I think "difficult" is a bug and not a feature. I will take a big objection to it and claim that this is a very big part of the problem. It is rewarding complexity over simplicity.

    There must be many papers, but I have seen at least two stoc/focs papers where a complicated proof was submitted when a trivial proof existed. For one of the paper, the author of the existing papers co-operated and liked the trivial proof. So the trivial proof also appeared in Stoc/Focs. This kind of authors are good who augmented the scientific discovery process. They do not take advanatge of the inherent problems with Focs/Stoc, i.e., do not game the system.

    In the other paper, the authors hated the trivial proof. They did not co-operate. One of their complicated proof was incorrect but they kept sending incorrect versions until the Stoc deadline, knowingly. The stoc happened the trivial proof was submitted to the conference. The authors went to the extent that they raised the conflict of interest and indirectly criticized the trivial proof. There was some professional relationship but no personal relationship to require conflict of interest.

    Of course in the journal version on the website, the incorrect proof is removed, quitely. The trivial proof is termed "simplification" of their original proof. And their talks do not even mention the simplification but mention that the original proof is "magical", as if being "magical" is a feature and not a bug.

    This set of authors take the advantage of inherent unavoidable problems in Stoc/Focs review, even after the review process. They game the system, rather successfully, and some are even rewarded member of our community.

    ReplyDelete
  11. Dear Bill (and Blogowner),

    I think having an interface that looks like USENET group will be better. Then all the anony"mouses" will reply to the proper thread, rather than beginning with "to Anonymous 1234".

    This is particularly true as some of the recent posts seem to be more of "what do you think of ..." types.

    ReplyDelete
  12. Kamal, just to say that it is great to have someone in the community as brutally honest as you are. Too often unethical behavior remains secret because of a presumed need for "collegiality.

    ReplyDelete
  13. Is the community really driven by these conferences?

    Yes, but probably not in the way that Bill meant the question. CS, unlike Math say, is incredibly deadline driven. If we didn't have deadlines it almost seems that no papers would get written. Deadlines gives us an excuse to break away from the constant interruptions of classes/committee work and finally concentrate on research. They also are a great opportunity for peer pressure: when many of your peers are focused on a major deadline, you'll feel left out if you aren't too. Overall, without the pressure of major conference deadlines there would simply be a lot less research produced and a lot less quality work, at least in CS.

    ReplyDelete
  14. If we didn't have deadlines it almost seems that no papers would get written

    I don't understand something here. How come math people do publish papers, although they are not conference driven?
    By the above logic, either they wouldn't publish (which is false), or CS people all have different personality than all math people. I don't see any evidence supporting this.

    ReplyDelete
  15. > either they wouldn't publish (which is false),

    They would, though at a different pace and in a different form. Slowing down the publication process mean fewer papers, but the published papers are of better quality, though at the price of slowing down the progress as well.

    Concerning the personalities...math people do have many more single-authored papers than CS people, don't they?

    ReplyDelete
  16. Edward,

    I don't see any reason why CS should invent the wheel here.
    Fundamental questions in complexity theory are of a pure mathematical nature.
    I believe (though, I have no evidence, of course), that the progress in resolving these problems, and thus the progress in our field, would be faster if the TOC community would conform to the standards of math research (as you described it).

    ReplyDelete
  17. Anon 14 wrote:
    I believe (though, I have no evidence, of course), that the progress in resolving these problems, and thus the progress in our field, would be faster if the TOC community would conform to the standards of math research (as you described it).

    I am not sure. There are two differences:
    (1) much less mature field;
    (2) many more active researchers.

    CS is currently able to progress faster just because it is less studied and less deep sights are required. Replacing journals by conferences would not speed up math, but they still can (or they can't already?) keep CS progressing faster.

    There is a crisis of the lack of refereeing resources due to (2), but otherwise probably conferences are still very suitable for CS.

    ReplyDelete
  18. What I meant in comment 14# above was that it is better to switch from a system that is "deadline oriented" (i.e., highly rewards publishing a terrible amount of papers), into a system that rewards quality over quantity.
    This will enable more people to study fundamental problems in a timely manner (and not having in the meantime to publish a lot of less significant papers).

    I suspect that (at least one of the reasons that) the fundamental problems of TOC will not be solved, or even partially solved, in the near future, is that not many professional scholars investigate these problems seriously, due to their urge to publish many papers.

    ReplyDelete
  19. To Anon 14:
    Then the deadline-driven system should be replaced by some other system for (reviewed) timely publication. In CS, it is important to publish the result as soon as you obtain it in order to prevent inventing the wheel, because too many researchers work on the same problem in the same direction simultaneously.

    ReplyDelete
  20. Are the papers mostly good?

    Yes, but the converse is not true: not all the good papers make it in yet many in the field act as if they did.

    Is their a Name-School-bias? Is their a Name-person-bias?

    Yes, but not as big as most people think (see SIGMOD stats). Still, anonymous submissions would be a step in the right direction. By removing bias as well as the *appearance* of bias.

    Is their an area-bias?

    Yes. STOC/FOCS claim to cover all of TCS but clearly they don't. First, there are areas off the list of topics, second, certain areas are automaticaly granted a lesser status and hence have a higher threshold to cross. Top papers in any area are accepted more or less fairly. Is the next fuzzy bunch in which there seems to be a bias towards complexity style results and/or technical proofs.

    Is their a Hot-area-bias?

    Absolutely yes. The hot area changes over time though, sometimes year over year.

    Is their a bias towards novel or hard techniques?

    Some in the field are infatuated with technical difficulty. Just go back and read the archives of this blog to see how many people confuse difficulty with quality.

    Aside from the clearly good and clearly bad papers, is it random? Is even determining clearly good and clearly bad also random?

    Worse, it is not random but biased on the wrong parameters. One possible way to fix this is to select the bottom 10-20% of the papers at random from a group which includes those plus the top 10-20% rejected papers. This would erase non-quality biases while keeping quality more or less the same.

    Are there many very good papers that do not get in?

    *Very* good? No. Are there many papers which match the bottom half in quality that do not get in? YES!

    ReplyDelete
  21. On the positive side, conferences are more popular in CS probably means there is a lot more collaboration.

    ReplyDelete
  22. There is some hand-wringing about 'randomness' in the acceptance of 'borderline' papers at STOC/FOCS. Here are some factors that I have seen play a big role in acceptance/rejection for, say, the last 20 papers.

    The biggest factor that committees go for in these borderline papers, one that I have not seen discussed in previous postings, is 'novelty'. This can be very different from some abstract notion of 'paper quality'. Novelty may be in the problem definitions or the techniques. At the borderline, committees will tend to choose papers with something particularly novel over safe papers that have good solid results that are similar in style to others at the conference. The feeling often is that it advances the field the most for the community as a whole to learn about novel ideas. This has an element of risk. In some cases papers are less novel than they appear or the novelty doesn't really lead anywhere. In other cases it can open up huge new areas.

    However, even novelty will not be enough if a paper is particularly poorly organized or hastily written. One of the difficulties with novel ideas is that people are not always coherent about explaining them the first time around. Overhyping novelty also has a way of turning program committees off. On the flip side, sometimes committees can get confused by novel definitions and mistake the claimed novelty for overhype.

    In any given year there will be fairly targeted research areas that attract ten, fifteen, or even twenty papers. In this case many papers will sound a lot like many other papers, in particular other papers ranked higher that have already been accepted. It can be tricky to tease apart how to rank the middle of the pack among this large number of closely-related papers since it is often a matter of taste. The problem is that if your paper loses within its popular area you are not going to win many novelty points when the borderline decisions come around if yours would be the n-th paper in the area. Exactly where a paper ranks in such a group can have a certain amount of randomness in it. (Note that from the committee's point of view small reversals in ranking in a group where differences are small has minimal impact on the quality of the conference, even though committees try to do this optimally.)

    The toughest decisions are for papers in areas that typically have few attendees and submissions and where the committee has few members with expertise. A critical factor in acceptance can be whether the paper is written in a way that might make it accessible to a wider audience, or attempts to place the results in context. This is not generally an issue with most of the areas that people have mentioned such as geometry or data structures, but it is an issue for logic.

    All else being equal, authors who already are represented among the accepted papers are somewhat less likely to have another borderline paper selected.

    ReplyDelete
  23. The idea of "fixing" STOC/FOCS is rather quixotic. It is hard to make a stronger case than that for increasing somewhat the number of STOC/FOCS acceptances, yet the number hasn't budged much in fifteen years. Think about it, the data is incontrovertible as the TCS community has grown substantially in size, both in NorthAmerica and worldwide and the change is rather minor (a minor increase in acceptances), still it makes no difference and those conferences go merrily along at the same size as before (so does SCG for that matter).

    For better or for worse, the solution to a problem with a conference is to create another conference. For example, since STOC/FOCS refused to grow we now have many other conferences of similar quality (SCG, LICS, SODA, etc) filling in the gaps.

    If Vijay thinks a conference with video submissions would be better (judging from SIGGRAPH, I doubt it) then he should go ahead and create his own.

    p.s. This is not a "love it or leave it" thing. It is just a pragmatical observation.

    ReplyDelete
  24. If we stoped writing conference paper and started to reward journal paper like mathematicians do,
    somebody in east europe must have solved
    the P-NP problem long time ago, but then
    theoreticians would be paid like mathematicians, which
    nobody here likes.
    Remember Perelman?

    ReplyDelete
  25. A concrete suggestion: increase the size of the PC. This would have the effects of:

    1. increasing community participation

    2. reducing load on PC members, theoretically leading to better reviews

    3. increasing representation of certain areas (also leading to better reviews in some areas)
    I don't really see any downsides. The only one I have heard is that people don't serve because they can't submit papers. But (1) why not allow 1 submission per PC member? and (2) even without implementing the first suggestion I am SURE there are plenty of people who would happily serve on the committee anyway.

    ReplyDelete
  26. A concrete suggestion: increase the size of the PC.

    This makes perfect sense, but it won't happen. I've seen members of the community which often serve in STOC/FOCS PCs argue for this and even they get nowhere.

    ReplyDelete
  27. PC sizes have increased in
    recent times. There are two
    counter arguments to increasing
    the PC size much further. First,
    this deprives the conference of
    potential submissions from
    PC members. Second, it is
    already difficult to have a global
    view of the submitted papers
    to make reasonable decisions.
    Increasing the size will make
    this harder.

    ReplyDelete
  28. As a rough point of comparison, FOCS/STOC seem to get about 300 submissions and have roughly 20 PC members, while Crypto/Eurocrypt get about 200 submissions and have roughly 30 PC members.

    Assuming each papers is assigned to 3 PC members, this means 45 papers/PC member for the former as compared to 20 papers/PC member for the latter. This is a huge difference!

    ReplyDelete
  29. Remember Perelman?

    if Perelman was a CS guy he surely would write dozens of FOCS papers like "5n circuit lower bound for Clique".

    ReplyDelete
  30. PC sizes have increased in recent times.

    PC sizes have crawled from an average of 15 around 1995 to an average of 18 today.

    Second, it is already difficult to have a global view of the submitted papers to make reasonable decisions. Increasing the size will make this harder.

    As a PC member I read 45 papers out of 275 submissions (16%). If we increase the PC size to 25 then the load is 33 papers out of 275 (12%). You mean to tell us that the 12 papers in the difference are critical in having a global view of the submitted papers? I don't buy it.

    ReplyDelete
  31. I don't understand something here. How come math people do publish papers, although they are not conference driven?
    By the above logic, either they wouldn't publish (which is false), or CS people all have different personality than all math people. I don't see any evidence supporting this.


    Not only is the personality of the field different, but the people themselves are in fact very different. CS is a young field. While there are some big questions and some theory-building that takes place, a large part of the research is problem-solving driven rather than theory-building driven. Also, there is a much larger connect with the real-world. Due to both these factors, the field is much more fast-moving.

    The other aspect is the interactions. The collaboration graph in CS is significantly denser than that in math. Conferences are a focal point where many of these collaborations begin.

    The personality of the papers itself is also very different from math. Most papers give some motivation for the problem being studied, give an outline of the techniques used, and usually try to give some intuition for the proofs. This, I think, certainly benefits the community, and happens in a large part due to the conference review process---you have the convince three PC members who are not necessarily experts in the subarea that this is a valuable contribution, which takes more work than convincing three journal reviewers who are intricately familiar with the subtle technical details of all papers in the subarea. As a result of this, a much larger audience can understand the work. Other than the obvious benefits, this significantly helps techniques from one subarea to be used in solving problems in other subareas. It is no surprise then that quite a few open problems in math have been solved by CS people, and proofs of many theorems have been considerably simplified by CS people.

    ReplyDelete
  32. thank you very very much thank you very very nıce...

    ReplyDelete
  33. I guess that i'm not saying something new -- sorry but I don't have time to read all the previous comments.

    there are many arguable ways to improve the accpet/reject/review/PC/ mechanism.
    The simplest and yet satisfactory way is to let the reviewrs to see others' review, and update it accordingly.

    It might be the case that the old versions might be saved in the stoc/focs site -- just to encourage originality ....

    ReplyDelete