Umesh Vazirani: should publishing in STOC/FOCS and Science/Nature be mutually exclusive?

The business meeting of STOC/FOCS is usually rather tedious, but it is also an opportunity to raise and debate issues that the community should be concerned about. One such issue is the inconsistency between our publication norms and the norms of other communities. This is becoming more and more important as TCS megalomaniacally adopt the “lens on the sciences” point of view. Towards the FOCS 2013’s business meeting, Umesh Vazirani agreed to write a guest post on this subject. While Umesh mentions Science and Nature, this is relevant to other communities (Econ journals come to mind).

I would love to encourage the readers to start the debate by commenting here. Please remember though that WindowsOnTheory maintains a policy of keeping the discussion respectful and on point. And now to Umesh:


Here is a recently discovered theorem about STOC/FOCS: the rules spelled out in the STOC/FOCS CFP imply that you cannot have a STOC/FOCS paper whose journal version appears in Science or Nature. Authors are forced to choose: if they choose Science/Nature then our community suffers since we do not get to hear about some strong papers and new directions; if they choose STOC/FOCS, then it diminishes our community’s influence in the sciences.

This is not a purely theoretical concern. There was already a paper that we submitted to ITCS instead of FOCS 2012 for such reasons. It appeared in Nature earlier this year: But the new STOC/FOCS theorem was only fully proved in the context of a paper by Thomas Vidick and myself that resolved a longstanding challenge by Myers and Yao about device independent quantum cryptography. That paper was accepted to STOC, but the subsequent proof of the STOC/FOCS theorem led us to withdraw the paper and we are now in the process of submitting it to Science. Both these papers represent the kind of computational lens on the sciences kind of thinking that our TCS community should be actively engaging in and taking credit for. The phenomenon is not restricted to those two papers – a number of other papers have since chosen to forgo the STOC/FOCS route for the same reasons.

There are two basic issues: the first and larger one is that STOC/FOCS explicitly bans journal publication before the date of the conference. The motivation cannot be suspense, the arxiv has long rendered that moot. It is also clearly not an issue of “double publication”, in view of the long accepted norm that papers appear in both a conference and a journal. ACM and IEEE copyright policies might have been implicated, but a close reading of those policies reveals that they treat journals and conferences symmetrically, and so have no implications for the order of publication.

The second issue has to do with the recently formalized (or invented) policy of STOC/FOCS to insist on the publication of a full 10 page abstract in the proceedings as an obligation rather than as a privilege. By contrast a 1 page abstract with a pointer to a full paper on the arxiv would not preclude publication in Science/Nature after STOC/FOCS. One could go much farther and note that conference proceedings, which were once the life blood of the theory community, have been increasingly marginalized by the arxiv and the web. A sensible policy would be to take STOC/FOCS proceedings online, with pointers to papers on the arxiv. Without compromising any of the attributes of the current proceedings, this would have the added benefit of reducing the time between abstract submission and conference date, thereby leading to the inclusion of more up to date results in the conference.

Whatever the theory community decides, I hope it will be an active scientific decision rather than the current bureaucratic default.

31 thoughts on “Umesh Vazirani: should publishing in STOC/FOCS and Science/Nature be mutually exclusive?

  1. I didn’t fully understand the second issue. Is it that Science/Nature do not want to publish a paper that already has a 10 page abstract in the STOC/FOCS conference proceedings?

  2. I didn’t fully understand the second issue. Is it that Science/Nature do not want to publish a paper that already has a 10 page abstract in a conference proceedings?

  3. Jelani: The answer to your question is yes to some extent. Science and Nature won’t announce something that has already appeared elsewhere with a DOI number. However, by reworking things a little, for example with an aspect of a survey, or putting a small different twist on things, it is possible to do both.

    This general question was on the agenda at the STOC 2013 business meeting in Palo Alto but the car fire that brought the meeting to a premature end pre-empted the discussion. The SIGACT executive committee, in consultation with a number of others including several former PC chairs, were going to propose an interpretation of the existing rule on journal publication that would not preclude prior publication in journal-like venues such as Science and Nature that are primarily in the form of announcements of results rather than refereed journal publications containing full proofs, which is what the “no prior journal publication rule” was designed for. It seems to me that this kind of interpretation of the sense of the “no prior journal publication rule” might even be something that would be reasonable for this year’s STOC PC to implement, though I would have preferred to have gotten the clear concurrence of the community at the business meeting.

    We would welcome discussion of this interpretation, which was pre-empted at the meeting.

    (On the specific situation about the proposal to withhold part of the 10-page core of a submitted paper (particularly for STOC 2013 where submitted papers were explicitly required to be presented in final version format) seemed like a “bait and switch” that would have been unprecedented for STOC/FOCS and neither the STOC PC nor the SIGACT EC felt was appropriate)

  4. So, if it is allowed to submit such an “announcement” to Science/Nature without full proofs AND and “extended abstract” to STOC/FOCS AND a journal version to a TCS journal, then wouldn’t that make us look like we are a community that pads our resumes with repeat papers?

    Also, with all due respect, I think the following argument is a bit exaggerated:
    “… if they choose Science/Nature then our community suffers since we do not get to hear about some strong papers and new directions;…”

    Not being presented at STOC/FOCS does not mean the community does “not get to hear about” the result. Put the paper on the arxiv and no one will “suffer”. The only tragedy is the lower STOC/FOCS paper count of the authors.

  5. I completely agree that we should encourage the (what Omer calls “megalomaniacal”) algorithmic lens. As an aspiring cstheorist, that is my hope and I’ve tried taking steps towards it, just not at the difficulty level of STOC/FOCS(, yet). However, I don’t think reforming STOC/FOCS to be more in line with Nature/Science is the way to do. Although there might be other reasons that some people might want to reform STOC/FOCS. Here’s why:

    [1] STOC/FOCS and Nature/Science have completely different focuses.

    A STOC/FOCS (SF) paper in its usual appearance will never make it into Nature/Science (NS) and vice versa (there might be some massaging possible with quantum computing results).

    In my reading of NS (which usually concentrates on parts of mathematical biology close to evolutionary game theory), mathematical results or intuitions are not prized, always relegated to supplementary materials, and usually not read. This can be clearly seen from Wilson group selection debacle where there was a great mathematical supplementary material, but a conclusions in the main paper that didn’t follow from it. All the numerous subsequent discussions focused only on the main body of the conclusion, and rarely discussed the math. As far as I can tell, in NS mathematics is never the result but merely a line of evidence used to support some extra-mathematical conclusions. It is this conclusion that NS publishes, and it doesn’t matter by what means it was achieved.

    SF, on the other hand, seems to prize difficult and technical mathematics, with applications and extra-mathematical conclusions often left as window dressing in the motivation section. To me, this is the exact opposite of the NS mentality, and it should not be taken as a downside. In mathematical biology, among big-wigs there seems to be a common practice: the flashy general conclusions are published in flashy general journals like NS, but the tools developed and the technical results are often published at the same time in field specific journals (say Journal of Theoretical Biology). Why can’t we do the same? Publish the difficult proofs and new techniques in SF, where other cstheorists want to learn them, and the extra-mathematical conclusions in NS if they are of interest to the general scientific community. It might seem like getting twice-the-bang for the same buck, but in fields outside of say quantum computing, it actually takes a lot of effort to convince scientists that they should take cstheory results seriously.

    This is also essential from the point of view of getting work reviewed properly. I have read several papers in NS that make common mistakes when talking about computation. How can we expect them to properly review technical cstheory results of the sort that would usually appear in SF?

    [2] If we really want to make an impact with the algorithm lens, we should not be aiming for NS.

    Even in fields that regularly interact with NS, there seems to be a love-hate relationship. Papers in NS get cited a lot, and so it can make an academic’s career to publish there. On the other hand, NS is also seen as a glam-rag: journals that publish flashy results because they are shiny, not because they have any technical merit. Of course, this might just be envy.

    I think that if we want to make our work relevant to other scientists, we should publish in top field-specific journals of the field we are viewing through the lens. For example, let’s look at Valiant’s model of Evolvability. I think this is a very pretty model, and very intuitive for a computer scientists. However, from my experience with talking to biologists, it simply doesn’t use their preferred metaphors and ways of thinking about evolution. It brings in some new ideas that I think would really revolutionize parts of evolutionary modeling, but on the other hand it also makes some classical mistakes that biologists are well familiar with.

    If an NS version of that result was published, then I fear most mathematical biologists would write it off as “sexy cstheory megalomania” because the mistakes are easier to spot than the deep contributions. However, if the paper was instead sent to a biology specific journal “Evolution”, “Journal of Theoretical Biology”, or “Genetics” then it would benefit more from the peer review, and because of it become phrased in a language much more familiar to mathematical biologists. After publication, the same experts would read it (since almost every mathematical biologist working on models of evolution keeps an eye on NS an the three specific journals I list), but in the latter case it will have gotten in because of technical merit relevant to the field and not because of sexiness. As such, it will be more likely to be used in the long term, instead of just cited in paper intros.

    1. Thanks for the insights. I want to clarify that I used “megalomaniacal” positively. I care a lot for the computational perspective we can bring to other fields.

      I also want to qualify “SF, on the other hand, seems to prize difficult and technical mathematics, with applications and extra-mathematical conclusions often left as window dressing in the motivation section” by emphasizing that difficult and technical mathematics is far from being all we care about. But this is for another discussion, and your point is still very useful.

      1. However technical difficulty seems to be a requirement. I’ve seen more than one paper rejected from those venues in which the comments are positive all around in terms of relevance, interest, etc, but the paper gets rejected because “techniques are simple”.

      2. While technical novelty is valued I disagree with the statement that “technical difficulty seems to be a requirement.” But this is not the topic here so I do not want to derail the discussion.

  6. Our community indeed has different norms, and our conferences as well as our journals are different than those of other communities. We have invested quite a bit of effort convincing the outside community that our conference publications should still count as “real” publications (I for example found myself arguing this in a committee that gave awards to students of different areas). Umesh, aren’t you worried that allowing these 1-page announcements in FOCS/STOC will hurt our students and other junior researchers? There may be internal reasons to revise our publication culture and possibly move to a model where conferences play a different role, but I wonder if it should come to answer external pressures (imposed by the norms of other communities).

    There may be other solutions, such as that Paul discussed. I would like to add another partial solution which is to co-locate various workshops with FOCS/STOC (an idea that has been floating for some time). This will allow the FOCS/STOC community to be exposed to work that appeared elsewhere (Science and Nature, an Econ journal, or even more specialized conferences such as CRYPTO). This will not give authors the FOCS/STOC cv line (though these workshops can still be exclusive), but may still give the relevant exposure.

  7. First let me correct something that Paul Beame said above. Nature/Science are refereed journals and not mere announcements of results. Here is what the editor of Nature wrote to us:
    “I should stress that it is not the purpose of a Nature paper to serve as an advertisement for more technical results published elsewhere. Rather, the Nature paper must be able to substantiate its claims – often, this takes the form of a conceptual discussion in the text, with quantitative proofs provided as formal Supplementary Information (SI).”

    Paul’s comment may also have led to the misunderstanding by “tranquilized” above, where he refers to the publication of an “announcement” in Nature/Science followed by STOC/FOCS followed by a TCS journal. The publication in Nature/Science is the journal publication, with no TCS journal publication to follow.

    In response to Omer’s question above about whether I am worried that 1-page announcements in STOC/FOC would dilute STOC/FOCS papers’ claim to count as “real publications.” I would have thought that the main argument in support of viewing STOC/FOCS as legitimate publications was a scientific one: namely, that papers that are accepted to STOC/FOCS are refereed and the conference is very competitive. I am not sure how much the argument changes if instead of an extended abstract there were a one page abstract (or for that matter a single paragraph or even just the title) in the proceedings with a pointer to a paper on the arXiv. As I said in my post above, the significance of conference proceedings have been greatly eroded by the arXiv and the web. This may be a good time to sensibly address the larger issue about how they should evolve to keep up with the times.

    Finally in reference to the emphasis on the “line on the cv” among many posts above: while I agree it has some significance, it clearly hasn’t stopped several people from forgoing the STOC/FOCS route in response to their current unfortunate policy.

    1. I agree that we should address the larger issue of adapting our conference system with technological advances. (In fact, I expect another guest post on this topic.) But in the meanwhile, if the “line on the cv” is not that important then why wouldn’t my suggestion of an adjacent workshop system solve the problem you raise?

    2. I agree that Nature and Science think of themselves as publishing the definitive versions of articles, without any need for a more detailed or carefully checked version to be published elsewhere. However, for proof-based papers I do not trust them to ensure careful refereeing. Any given paper might have been refereed just fine, but the reviewing process at these journals cannot guarantee such an outcome with anywhere near the same likelihood as a top TCS journal. This means I think of Nature/Science publication as being much more like publishing in a top conference: the paper must meet a high bar for interest and importance, but one can’t count on detailed, carefully checked proofs. Publishing the full version in a TCS journal still has value. (So I’m sympathetic to the goal of keeping conference publication from precluding journals like Nature and Science, but I wouldn’t want this to replace publishing in TCS journals.)

      Incidentally, what became of the supplementary information for the Reichardt-Unger-Vazirani article ( The paper refers to the SI twice for proofs, but I can’t find it anywhere. Maybe I’m being silly or just don’t know where to look, but I can find it for some other Nature papers (for example, there are links to several hundred pages of supplementary material at the bottom of Fortunately, there’s a reference to the 100-page arXiv paper, which I imagine contains the same content as the supplementary information, but I wonder whether the SI is missing on the paper’s Nature web page.

  8. maybe this was an exception? or did the policy change recently? or was the order different?

    Jon M. Kleinberg: The small-world phenomenon: an algorithm perspective. STOC 2000: 163-170

    Jon M. Kleinberg: Navigation in a Small World. Nature 406(2000), 845.

  9. it certainly important to our community to keep STOC/FOCS as a physical and virtual meeting place where we hear about some of the best results in the field. We should eliminate unnecessary bureaucratic barriers to some such results.

    My tendency would be to at least first follow the path of least resistance and see how we can tweak STOC/FOCS to accomodate such papers, rather than making more radical changes such as completely eliminating the proceedings or the rule of no previous publications. Maybe these more radical changes make sense in their own right, but then this should be discussed not in the context of the 1-2 papers per conference that might potentially go to Nature/Science.

    To me, allowing on a case-by-case basis for some papers to have a one page proceeding version with a link to the arxiv version (as is already done by other conferences) is a no brainer. If it’s not universal, but only for very few papers at the authors request and PC’s consent, that should mitigate Omer’s concern on it changing the nature or respectaibility of a conference publication. I think it would also address Paul’s concern on a “bait and switch” since it won’t be too much work for the PC to verify in these few papers that the arxiv version contains the material that was submitted and accepted.

    Allowing to submit to STOC something that was previously published/submitted to a journal is a more subtle matter. Again, on a case by case basis, and assuming there is a significant difference between the versions (and perhaps in the audience that the versions were intended to), I think this can sometimes be done. But otherwise, it is a change that deserves more thought.

    I can see arguments that STOC/FOCS should completely abolish the prior publication rule and also allow papers previously published in other CS conferences such as, say, CRYPTO – we’d certainly get some great results this way that otherwise wouldn’t appear in STOC/FOCS. But maybe this changes the nature of the conference too much.

    1. I’d be very careful about the option of a one page version with a link to the arXiv. I agree with Omer that even having this as an option could damage the rest of the world’s view of CS conference publications. For example, even in the adjacent field of mathematics there’s a lot of skepticism regarding whether conference publications should count as genuine publications. In my experience, it’s a powerful argument to be able to say “No, this isn’t just a preprint or a brief summary. It’s a genuine archival publication.” If some FOCS/STOC papers are not archival publications, but are instead literally a brief summary and a link to a preprint, then this will totally undermine that argument. Basically, if you manage to convince Nature/Science that some FOCS/STOC papers should not count as publications, then you’ll inadvertently convince the rest of the world as well.

      If you don’t want an actual publication in a particular case, then I’d suggest getting rid of even the one-page version. There’s no reason why a conference couldn’t have a couple of presentations that simply do not appear in the published proceedings. That would avoid the ambiguity of what counts as a publication (these presentations would not count), but the community would still hear about the results, and the speakers would still get the honor of having their work selected for presentation (they would just have to list it under talks rather than papers).

      The important thing is clarity: if something looks like a publication on a CV or in a bibliography, then it should still look like a publication under closer inspection.

  10. First, as was already mentioned, I find this discussion weird since papers eligible for both STOC/FOCS and Science/Nature are quite the exception! Quantum computing may be the only CS subject really concerned about this issue because quite a lot of QC papers may be published in both FOCS/STOC and Science/Nature.

    My second point is that it is time for computer science to grow up, and I think that this would make the issue we are discussing irrelevant.

    Lastly, I find the discussion about the issue of publishing one-page abstracts with an arXiv link in the proceedings a bit weird too. The fear of some of the commentators is that it would decrease the prestige of the conferences because papers in conferences then could not count as “real papers” anymore. But what about the fact that many (most?) papers in FOCS/STOC are publish without all the proofs? This makes papers in conferences non real papers to my mind. This is in some sense inherent to the conference publication, and I totally agree with mathematicians for instance that conference papers should not count as much as journal papers. Of course, this does not mean that a paper in a CS conference should count as few as an abstract in a math conference!

    1. There is no basis to back up the statement “mature sciences publish in journals” any more that “mature sciences publish in journals with names in Latin”. There might be many good reasons to move away from conferences to journals, but “older sciences do it” is not high in that list.

      The best proposals I’ve seen attempt to keep the best of both worlds, such as PVLDB.

  11. First, as was already mentioned, I find this discussion weird since papers eligible for both STOC/FOCS and Science/Nature are quite the exception! Quantum computing may be the only CS subject really concerned about this issue because quite a lot of QC papers may be published in both FOCS/STOC and Science/Nature.

    My second point is that it is time for computer science to grow up, and I think that this would make the issue we are discussing irrelevant.

    Lastly, I find the discussion about the issue of publishing one-page abstracts with an arXiv link in the proceedings a bit weird too. The fear of some of the commentators is that it would decrease the prestige of the conferences because papers in conferences then could not count as “real papers” anymore. But what about the fact that many (most?) papers in FOCS/STOC are publish without all the proofs? This makes papers in conferences non real papers to my mind. This is in some sense inherent to the conference publication, and I totally agree with mathematicians for instance that conference papers should not count as much as journal papers. Of course, this does not mean that a paper in a CS conference should count as few as an abstract in a math conference!

  12. To answer Omer’s earlier comment, I think Umesh’s main point in motivating publication in Nature or Science is to increase visibility of TCS results to other communities. Your suggestion of adjacent workshops seems to attempt to achieve the opposite, which is to “allow the FOCS/STOC community to be exposed to work that appeared elsewhere”.

    Fortunate or not, it is a fact that Nature, etc., publications get read by many communities; as critical or dismissive as readers may be papers published there do reach a very wide audience. Many results from our community would I think benefit from the exposure that results from publication in such venues. It is not only about lines on CVs, but really about making meaningful contributions. In fact, the “re-writing exercise” described by Artem Kaznatcheev (a paper written for Nature must take on a very different format than one written for STOC) can be very fruitful one; maybe it is an exercise we should constrain ourselves to go through — when appropriate.

    I don’t think anyone is advocating that most or even a “significant” fraction of the papers that make it to STOC or FOCS should appear in Nature. The point is that maybe a very small fraction should, or at least could, and it is a shame that archaic policies combined with the desire (necessity) to have STOC appear frequently enough on one’s CV should prevent that.

    I also don’t see any conflict between this and the necessity of maintaining high standards of rigor and correctness for our papers and proofs. Many conference papers never make it to a TCS journal, and even when they do I am not sure how much more through the refereeing is. Relying on journal publication as a guarantee of correctness is in any case a bad idea: better have a standard of publishing detailed papers on the arXiv, and have a mechanism for “crowdsourced” checking attached to that, as I believe will build up by itself over time (see e.g. scirate). Standards for the quality of a written paper should be imposed by the community and not delegated to STOC PCs, Nature editors or Journal referees.

  13. To clarify my opinion, I agree that physical conference proceedings are losing their value, and for that matter also physical journal volumes. I think Umesh is suggesting to get rid of the physical proceedings while maintaining the selective nature of these forums. I believe that in one form or another, this is where we are going. I am only worried about the effect on junior people if the transition is not done with care. I think Henry said it very well: “if you manage to convince Nature/Science that some FOCS/STOC papers should not count as publications, then you’ll inadvertently convince the rest of the world as well.”

    Boaz and others, I don’t think we are talking about a couple of papers. If we will allow a 1-page abstract track (similar to EC) then a non-negligible fraction of papers will take it (and FOCS/STOC PC cannot be expected to discriminate). I think it may be wise to separate such tracks a bit more, either according to my suggestion or according to Henry’s.

    Thomas, I fail to see the distinction between a Nature/Science paper that get exposure in FOCS/STOC and a FOCS/STOC paper that get exposure in Nature/Science. We are simply talking about allowing papers exposure in both Nature/Science and FOCS/STOC.

    1. Omer,

      My reply was with respect to your suggestion of co-locating broad workshops with STOC/FOCS. I meant to say that such a possibility would not help give exposure of our STOC/FOCS works to other communities, but rather the opposite. For this we would need a Theory/CS workshop co-located with, say, one of the APS meeting…

      But maybe I misunderstood your point: did you mean to say that authors from Theory/CS could always publish in Nature, not in STOC, but still present their results to the STOC audience in one of those co-located workshops? In that case you could even imagine STOC itself having a special session dedicated to “outreach”, or “broad papers”, in which would be presented papers having a definite Theory/CS core (possibly mostly papers originating from the community itself), but for some reason or another were already published in another venue, targeted to a different audience than ours. Such papers would be subject to refereeing, but may not appear in the proceedings (other than their title and authors). This could be a nice solution: authors would still get some kind of a STOC/FOCS label&exposure (though they would be clearly distinct from the standard batch of accepted papers), and STOC/FOCS attendees would get to see some (hopefully) wide-ranging applications of interesting theoretical work. (It seems so far such talks have been confined to one invited talk per STOC/FOCS, so it would just be a question of extending that slot slightly by including the possibility in the CFP).

      1. Yes, this is exactly what I mean (and the exact implementation is less important to me at this point). I would love to see FOCS/STOC being as inclusive as possible, both in the research that gets presented there as well as in the audiences it attracts. This does not necessarily means drastically revising the FOCS/STOC core, but could to a large extent be achieved by augmenting it.

  14. I can see Henry and Omer’s points. I think it is indeed better to have a clear separate track for papers that have appeared elsewhere (or are going to).

    Probably the best thing would be if the papers go the same refereeing process and should be presented as part of the conference, and perhaps a one page version + link should be in the proceedings, but they should be of a different type, and it should be clear from looking at someone’s CV to know which track the paper appeared in.

    I agree with Omer that conference proceedings will probably die a natural death at the not too distant future, but the transition should be handled with care.

  15. I don’t understand. Umesh writes that he submitted the Nature paper to ITCS. Does ITCS have a different policy than FOCS?

  16. ITCS does have a different policy than STOC/FOCS. That policy (in conjunction with that of STOC/FOCS) has made ITCS the conference of choice for computational lens type papers. Let me spell out the essential elements of such a policy:

    1. No restrictions in call for papers about whether papers are submitted/published in journals before the conference. But the author must notify the program committee about the prior journal publication. Note that this does not open the door to “double publication”, since the paper is still appearing only once in a conference and once in a journal (the order is now unrestricted). In particular it would not change the policy about papers that were previously published in CRYPTO, etc.

    2. Authors may choose to submit a greatly shortened version of their paper for the proceedings. But then it must include a link to a more complete version that is available at a public archive. Note that this does not involve getting rid of conference proceedings. There is a separate issue about how best to organize conference proceedings (again without getting rid of them) in view of all the capabilities afforded us by public archives – that is a separate discussion, but also one that is long past due.

    Omer, in principle I am open to a policy of a special session at STOC/FOCS for these papers. But I must confess it seems a little complicated to me. Can you spell out a concrete proposal.

    Finally, I can appreciate the feeling of wanting to tread carefully to avoid any adverse effects on junior people in the field. But as Omer and Boaz say above, conference proceedings are going to have to change in the near term, regardless of what we do about the issue at hand. So it seems reasonable to assume that changing the policy along the lines of item 2 above wouldn’t have a large impact on how STOC/FOCS publications are viewed in the larger CS community in the near term. Omer, you say above that if there was such a change in policy along the lines of item 2, you feel that a significant fraction of authors will exercise that option. That has not been the experience so far at ITCS. We could approach this question empirically, if you are able to email authors of papers in FOCS 2013 to ask how many of them would have chosen this option for their papers if it had been available to them.

    1. I don’t see the complication. Authors should specify at submission time, which of the tracks they want to take. The talks of the two tracks could/should be mixed, but only the traditional track will be published in the proceedings (the proceeding can specify a list of the other papers, and the website can link to their electronic version). I would in fact prefer that the new track will be separated as a workshop (which essentially it is). The talks can still be mixed and the same PC can handle both (or two PCs can be appointed). I would suggest that this workshop will feature only papers that are aimed at communities with different publication practices but also strong work that appeared in other more specialized communities. This will be an opportunity to bring back researchers and directions that “left FOCS/STOC” (my examples come from crypto but I know there are many other examples).

      At first, people that would like to be able to list a FOCS/STOC publication in their CV will still choose the traditional track. If in time, more and more papers will aim at the new track (the workshop) workshop rather than the old track (the conference) then this will be a gradual transition towards the end of FOCS/STOC as it is currently is and the beginning of FOCS/STOC as a selective but open workshop.

      Regarding my estimate that more than 1,2 papers would prefer a 1-page paper in proceedings if allowed, I would start by mentioning game theory papers (that may want to keep the door open for some of the Econ journals). I would also say that over time, some specialized conferences may choose to allow publication to papers that appeared in FOCS/STOC as 1 page (as they allow for workshops with similar practices).

  17. Below is what the ITCS’2014 cfp states regarding prior and simultaneous submissions and
    proceedings. I would not have thought that submitting to Nature (or a TCS journal) and then to ITCS would have been allowed under these guidelines. If it is allowed then the ITCS organizers should make it more explicit. I do not agree with the policy of having a Nature paper followed by an ITCS publication.


    Prior and simultaneous submission: Work that has been previously published in another conference proceedings will not be considered for acceptance at ITCS 2014. Simultaneous submission of the same (or essentially the same or overlapping) paper to ITCS 2014 and to another conference with published proceedings is not allowed. The program committee may interact with program chairs of other (past or future) conferences to find out about closely related submissions. Posting versions of the submission in freely accessible on-line repositories such as the arXiv, ECCC, or the Cryptology ePrint archive is allowed and encouraged.

    Proceedings: Authors of papers accepted to the conference must submit a version to appear in the proceedings. The proceedings paper should describe the results and essential ideas. If the authors choose, they may submit a greatly shortened version. But then the more complete version must be made available at a public archive and a link should be forwarded to the PC Chair.

  18. Anonymous above has very helpfully reproduced the relevant excerpt from the ITCS CFP. The policy on prior publication clearly outlaws papers that appeared in another conference proceedings, but places no restrictions on prior journal publication thereby addressing the Science/Nature issue.

    Why is it natural to invert our usual order of “conference then journal” in this context? The point is that the on average 9 month delay to publication in STOC/FOCS (6 months from paper submission to conference + 3 months on average to a submission deadline) becomes very significant when the time from submission to publication for a journal can be as short as a couple of months. This particular issue does not come up for TCS journals where time to publication is still reckoned in years.

  19. There are a number of good points in different threads. I agree with much of what Henry, Boaz and Omer have said. Henry has it spot on wrt how Nature/Science operate in a way that is quite different from the rigor of TCS journal reviewing. There is a cost in rigor in being timely, and Nature/Science reviewing shares this cost with our conference reviewing, albeit to a bit lesser degree. This is what I meant.

    The list of papers that have gone from STOC/FOCS or other venues to Nature/Science is much larger than the one example cited. It is possible to publish in STOC/FOCS first if one puts a different slant on things or produces a summary and refinement of a body of work. These are not mutually exclusive in that order, despite what Umesh’s message implies and despite the official Nature/Science policies that we mentioned earlier.

    The big questions to answer, which Boaz and Omer discuss tangentially, are what purposes selective conferences like STOC/FOCS should serve and how should these purposes be balanced in the context of limited resources: time and attention? I would say that current purposes in no particular order include:
    1.- bringing researchers together to hear about the best current papers
    2. – providing a common place for researchers talk with each other and build a sense of community
    3 – providing an in-person audience for a wide variety of researchers to talk about their work that is among the best current papers.
    4 – bringing together in one place a record of the best current work for non-attendees.
    5 – publicizing the best current ideas and proof methods so that others in our community may build on them.
    6 – providing a certification of approval for authors that their papers are among the best current papers.
    7 – publicizing our best current work to the world outside our community.

    Clearly Science/Nature do a better job at 7 than our conferences do and probably 6 as well. Should one doubly certify papers? If acceptance consists only of talks and lists of papers or even 1-page abstracts, then those outside the meeting do not benefit in the same way and we lose on 4 and 5. If we have different kinds of papers, how would you balance this against another paper? Should one judge them by the same standard?

    I like the idea that Boaz and Omer discussed of having a sampler of theory-oriented papers from other venues (not in the proceedings) that might precede the conference, just as we do for tutorials and workshops. This way, we don’t cut into the precious time slot resource. It would be parallel to these other activities so these talks wouldn’t be elevated above the regular conference talks. One could have submission/invitation for this.

Leave a Reply to Paul Beame Cancel reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s