Future of STOC Proposal

During the past year the SIGACT Executive committee has considered the issue that the STOC conference no longer attracts a large segment of the theoretical computer science community. Lance Fortnow wrote a proposal for restructuring the STOC conference to focus on bringing the theory community based on the model of large non-CS scientific conferences that accept all reasonable submissions, with many parallel sessions and plenary and invited talks. You can read the full proposal here.

The proposal had some support and some opposition in the executive committee. We did decide to circulate the proposal to approximately thirty members of the theory community. You can read many of these responses below. 

Based on the responses, the SIGACT Executive Committee decided to start with a mild change, increasing the number of allowed submissions from about 80 to 90. 

The above was presented at the STOC 2010 business meeting to mixed reaction. Some at the meeting suggested I open up the discussion. We encourage you to add your comments to this post or the responses and keep the discussion going.

Paul Beame

I am afraid that I don't understand the value in your specific model for STOC and in net am very negative about it.  
That doesn't mean that I am opposed to STOC changing modes, though I admit to having an affection for its current role.   I would expect  that your current proposal would not be popular at a business meeting.  (Unfortunately I will not be able to attend STOC since it conflicts with my son's high school graduation.)   The two-page "papers" would be worthless.       As far as I am concerned this proposal would be tantamount to the removal of STOC as a serious venue for publication.     This would be a loss to the community in speed of dissemination.  Though it might be OK for math departments the whole notion would be at odds with the publication standards of the rest of Computer Science.     

If you are to pick a broader model I would choose something from successful large conferences in less math-oriented fields like ISIT or NIPS.    NIPS has a different levels of acceptances as well as many subsidiary workshops.    ISIT has regular though fairly lax reviewing and no limitation on multiple submissions.      Both have real proceedings.   

* One important note, no matter what the proposal:  If the selectivity of the conference is to change so significantly it ought to modify its name so as not to devalue the selectivity of earlier publications.   After all, CS promotion committees, egged on by the CRA, have given special dispensation to conferences like STOC and it would be very negative for the evaluation of previous work if the standards dropped so precipitously..  

Some other considerations that you do not discuss but seem essential to making a larger broader conference work.

* if the conference is to be so large then it will be beyond the ability of the current local organizers to run.   You will need to have it run by the ACM or something similar rather than by volunteers.     

* I can hardly imagine such a conference running for only 3 days.   This would require a shift to later dates when more of the community can make it to the conference without having to skip many classes.   This would force the conference to be held between June 15 and Aug 25 or so.   (Our classes go until June 13 for example and others start a week before Labor Day.)

In talking with Richard Ladner about trying to get a conference that would attract all of theory I realized that maybe trying to change STOC isn't required to do it. How about doing a Federated SIGACT Conference in the latter half of June 2013?    You could try to get:


I would hope that this would be a chance to bring SoCG and PODC back in contact.  The timing works out wrt Europe vs North America for CCC.  I am not sure about the rest.

We could have plenary Theory speakers and we'd need ACM to run the arrangements but by being way smaller than FCRC we could have lots of choice of venues in smaller cities.   We could run the whole thing in 5-6 days in the right location.   You might have a more liberal "SIGACT" track (though with the other conferences it might not be necessary.)

We'd need a location that didn't require that we provide food all the time so that we could keep registration fees low.

Russell Impagliazzo

My initial reaction is that this would be a huge mistake on the part of the
community.  STOC/FOCS is a well-respected ``brand'' among computer scientists,
including chairs, deans, and funders.  Diluting or making ambiguous the meaning of
a FOCS/STOC paper will have  a negative iimpact on the careers of all researchers in 
TCS, not just junior researchers.   If you want a conference along the lines you suggest in this proposal, why not create a new conference rather than changing the meaning of the name STOC dramatically?  If the new confernce overshadows STOC, then we can 
eliminate STOC later.  

I would not submit papers to a conference as in the proposal, under any name, or encourage my students to submit to it.  It seems to provide no additional benefit
over  having the paper in ECCC, and giving talks on the paper at university seminars.  
I might attend such a conference if it were conveniently timed and located, but would 
not go out of my way to attend.  I would not want to be on the program committee, if it requires one.  

If others reacted like myself, the main effect of the proposal within the theory community would be to merge FOCS/STOC into a single annual conference callled FOCS.  This
conference would be fiercely competitive, having an acceptence rate below 15%, unless researchers decided that it wasn't worth the gamble/wait and submitted their papers to
specialized conferences instead.  

As I mentioned above, the effect outside the theory community would be to make it harder to judge the quality of a theorist's publication record.  It would take some time before 
the distinction between ``old STOC'' and ``new STOC'' percolated to be general knowledge, and even then, the question of when the switch over occurred would have to be answered. 
If the graphics community changed say, SIGGRAPHICS to a non-competitve forum, it would be a while before I caught on, and would permanently impair my ability to judge a CV from graphics candidates.  I imagine the same thing would happen to non-theorists if we switched STOC to a non-competitive forum.  

I do not see any positive consequences at all.  Since I would not submit papers, or be
giving talks, going to such a conference would be a low priority for me, and I imagine
it would be likewise for colleagues that I am eager to talk to.  Thus, I can't see that
attendance will soar rather than drop percipitiously.

While there are always imperfections and small improvements and experiments are needed  in any human institution, STOC/FOCS as a bi-annual conference has been a
tremendous success so far.  They are the type of prestigious conferences that other areas have emulated.  People within and without theory know and respect puiblications in
these conferences.  Perhaps some of this respect is unwarrented, in that conference referreeing is short of journal refereeing, and program committees are fallible.  However,
I cannot see any benefit to moving towards the changes in the proposal, and see the possibility of significant harm.  

David Johnson

I sympathize with the goal of establishing a large meeting
that attracts a large proportion of the theoretical computer
science field and its leaders, such as the AMS meetings do for
math and similar meeting do for physics and chemistry, etc.

Unfortunately, I do not think it can be done.  Those meetings
in other fields have the advantage of being long-established
and built into everyone's mindset.  A new such conference does
not stand a chance, given the competition for travel money etc.
by selective conferences that provide prestige and publication
credit.  The current proposal appears to recognize this by
hiding the new conference under an old name (STOC), and essentially
killing the old conference (STOC) so that at least IT does not
provide competition for travel money.

However, even with the old name, the conference is unlikely to
thrive.  CS has a long history of accept-everything conferences
(Computer Science Conference, FJCC, etc.) dying out due to competition
from selective conferences.  The fact is, such conferences do
not tend to be technically rewarding, as anyone who has attended
the annual INFORMS fall conference will attest.  (It was partly
because of this that the selective IPCO conference was established.)

Consequently, I have serious reservations about the up-side of the
proposal.  And the down-side is extreme.  There are already widespread
complaints that many good papers do not get into STOC/FOCS/SODA.
This proposal would reduce the number of slots by 33% (50% if you
do not count SODA), thus greatly exacerbating what is already a
major problem.

So you can expect me to argue strongly against this proposal if
it is raised at the STOC business meeting (although I may not have
to as I do not think it will get much support).

There are, however, other and less drastic approaches that we
could take to address the same concerns.  One possibility would
be to add a half-day of poster sessions to STOC, with a much
less stringent threshold for acceptance.  I'd actually prefer
poster sessions to a series of 10-minute talks, since I could use
my time more effectively in seeking out results of interest to me, and
could have a much more interactive experience with the authors.
Other areas of computer science value such poster sessions highly.

Another idea is to piggyback a general theory conference onto FCRC.
FCRC was set up as our best approximation to a general CS conference,
recognizing that a new, general and non-selective conference was
bound to fail.  The fact that it does not occur every year is also
a plus.  The one non-selective conference that I do find worthwhile
attending is the International Math Programming Symposium, which
is only held once every three years.  Its relative infrequency
makes it less of a financial drain, and so it can attract a high
proportion of the leaders of the field.  Also, people typically
talk about their best work of the last three years, which raises
the level above that of an annual accept-everything event.
(Admittedly, it is also like the AMS meetings in that it has
long established itself as the event that everyone who is anyone
in the field needs to attend.)

Or, if we want to avoid all the competition for attention at FCRC,
we could, on a once-every-3(or 4)-year schedule, colocate STOC (and
perhaps other theory conferences, as we are doing this year in Boston)
with a new conference that combines a major collection of invited
talks (as a draw for the experts) with an accept-everything, multiple
parallel session, schema.  Or perhaps the best thing might be to
do a one-off, in celebration of some noteworthy historical event,
fill it with big name invited speakers, etc., and see what happens.
If it is a success, we could think about doing it again.

Jonathan Katz

In writing my piece about "the future of STOC" I am responding to the specific recommendations of Lance's proposal but I also have the luxury of taking some of the other responses into account. To some extent, I have tried not to repeat points made extensively by others already.

To begin, I think we (as a community) need to decide what exactly it is (if anything) that needs fixing? In particular, I am not convinced that the goal of changing STOC should be to maximize attendance. (Oded Goldreich makes these points quite nicely.) While there are aspects of STOC (and FOCS, for that matter) that, in my opinion., do need fixing, I am also willing to concede that I may not be the "target audience" of STOC and I surely do not have the historical perspective that other responders have. In that sense, my opinion does not matter unless the larger community shares my concerns.

So what do I think needs to be fixed? There is the issue, raised also by Oded, that STOC and FOCS have become too focused on the competitive aspect of having a paper accepted than about the technical results being presented. There is the associated problem, both internal and external to the theory community, that someone may not be viewed as a "real" theorist without regularly publishing in FOCS/STOC. Then there is, perhaps, the most important question: what do attendees gain from attending the conference, and what should they gain? Should the conference be a social affair (in which case maybe maximizing attendance should be the goal)? Or should the goal be to learn, and to foster cross-pollinization of ideas across disciplines? I would prefer it to be the latter, and for me the conference currently fails.

In trying to analyze why that is the case, I hit upon two possible reasons:
(1) First, there appears to be an emphasis on technical "heavy lifting" at the expense of general interest to the broader TCS community. (As an aside, when I evaluate a paper for STOC/FOCS the first thing I try to evaluate is its interest to the broader community. I have been told explicitly by some people that I should not do this.)
(2) There is no time, nor is their motivation, for speakers and authors to make their results accessible to a broader audience. Both the above may go influenced by the competitiveness issue raised earlier, though they are not completely correlated.

I think accepting all reasonable submissions (as recommended in Lance's proposal) is exactly the wrong way to go, and would ultimately not address either of the points above (in addition to not increasing attendance). To me, one of the purposes of STOC (ideally) is to filter results for the community, altering the community to results of (potential) broad interest. Accepting all papers would also have the effect (as many others have noted) of diluting the meaningfulness of having a paper accepted. This means that people with "strong" papers will (a) not submit to STOC and (b) might decide to wait a whole year to publish at FOCS (which would lead to disastrous results, and only increase competitiveness). For these same reasons, I completely disagree with the claimed "Effect on Young Researchers" paragraph of the proposal. If a STOC publication means nothing (which will be the effect of accepting everything) then it won't help researchers at all to have a publication there.

Instead, I proposed something radically different here that would seem to address everyone's concerns. My suggestion was to accept fewer papers to the main track of STOC, with the stated goal of highlighting papers of broad community interest. In addition, however, there would be several associated "workshops" (whether they share the name STOC or not does not matter much) on specialized topics. Papers for these workshops could even be selected from among those papers submitted to STOC but not accepted for the main track. This would have the effects of (1) increasing the total number of papers accepted overall, while drawing back people from other disciplines who may have felt "marginalized" by STOC in the past, while at the same time (2) accepting fewer papers to the main track, thus helping to focus the community's attention on a smaller "core" of important papers. At the same time, we might be able to give longer speaking slots to papers accepted to the main track, and encourage the authors to devote more time to make their talks accessible to the audience. While I may be wrong, I think this proposal would also reduce the competitiveness overall, since it wouldn't be expected, say, that a graduating student would have several main-track STOC publications by the time they graduate.

Other comments:
- I very much like the idea of inviting plenary speakers to talk about groundbreaking results and/or to give tutorials, and I think this fits right in with my ideals for the conference and would also increase attendance. Like Oded, however, I often find open-ended "invited talks" less useful (although there are certainly exceptions...).
- It's not a bad idea to allow people to give short talks about their research and/or papers published elsewhere, in an effort to increase participation (especially among students) and attendance . But I don't see the need to institutionalize this with a review process that accepts everything. In other conferences, there is simply an informal "rump session" that accomplishes the same thing and doesn't force speakers to commit months in advance.

Noam Nisan

To start with, I like the basic structure of this proposal.  While I
do like the CS conference system, I have to admit that the pan-TCS
conferences are becoming less useful as the field widens, and,
nostalgia aside, innovation is needed to maintain a general TCS
scientific community.  The proposed new structure seems to me to
indeed fit well with the rest of the TCS ecosystem
(journals+FOCS+specialized confs+arxiv+...)  I do think that a
name-change may be in place, reflecting the new format though.  (Maybe
something like CTOC, pronounced just like STOC but with the C standing
for conference/congress/confederated?)

My main problem with the new format is that, as detailed now, it does
not seem useful enough -- why would I come or send a student there?
Going to STOC/FOCS now has a double benefit: both for the speakers
(they are indeed listened to and they get significant credit) and the
listeners (the talks are good).  These two advantages will be gone
with the new format.  I am afraid that the weakly stated "few plenary
speakers" and "tutorials" are a step in the right direction but too
weak to be a real attraction.  I think that significant new
attractions are required  to make this "fly":  Either a strong program
of invited talks (like in the Congresses of Math or of game theory --
but this may be expensive since these speakers may require funding)
or, my preferred route, a "federated"-spirit having may specific
workshops and specialized conferences either as part of the new STOC
or as satellites (as is starting to happen around EC for example).

Finally, if a major change will happen, I wouldn't miss the change of
putting in other innovations as well: from videotaping and
distributing the talks (at least invited ones), to encouraging
preprints-on-arXiv, etc.

Mihai Patrascu

I do regularly attend STOC and FOCS. In many cases, it is because I
have papers there, but I have attended several times without papers.
The reason is that it allows me to meet a large sample of people from
about half of the theory community, with whom I would like to keep in
touch. Thus, I am sympathetic to the idea of a large meeting. I say
half of the theory community because another half (of "my" theory
community) is covered by SODA and SoCG and have no contact with
STOC/FOCS (or vice-versa). I regularly submit and attend to SODA for
this community; but I do not usually attend or submit to SoCG, since I
find the crowd a bit too small to justify it. Again, this indicates
that I would be most happy with a general meeting.

That said, your proposal brings up two issues:
(1) creating a general meeting;
(2) ending the STOC conference.

The proposed hijacking of STOC to achieve (1) is scandalous, in my
view. Reputation dies quite quickly, so just naming it "STOC" would
not boost attendance, as much as you might want this to be the case.
If this proposal is adopted, how would normal CVs look like? Should
one list "Strong STOC" and "Unselective STOC" for conference papers?

Thus, let me discuss the possibility of ending STOC (gracefully) in
order to make time for a new general conference. Since the idea of
selected conferences will not disappear, this could have two effects:

(A) FOCS would become the only strong conference. Experience with
communities that have a single super-strong conference (SIGCOMM,
SIGGRAPH) suggests this is a very bad idea. Having one deadline a year
is not good for quick dissemination, and could lead to unproductive
levels of competition.

(B) Second-tier conferences would be boosted to "top level." SODA is
already not far, while CCC could conceivably reach that level. But
this outcome would be quite unfortunate for TCS, since it would
already deepen a large gap between complexity theory and algorithms.
(One would expect complexity theory to be the bigger loser, as it
would be viewed as "philosophy" by contrast to the "useful

To summarize, I think the goal of a broad meeting is laudable, but
ending STOC would be a rather unfortunate idea. There are many
alternative proposals. My favorite one would be to create broad
meetings through careful planning and colocation:

* SoCG should colocate with STOC. The time periods are very close, so
this is easily done. At this late stage, it seems that bringing SoCG
kind of geometry back into STOC/FOCS is unfeasible, so this is the
best possible outcome.

* STOC/FOCS should increase in size by ~20%, allowing room for top
papers in areas that are currently SODA-only. The same could be said
about "non-STOC/FOCS cryptography," which seems to be an excluded

* All conferences should have poster sessions.

Rocco Servedio

I have mixed feelings about the proposal.  I think there are strong arguments to be made for having a 'large science meeting' for TCS that is not exclusive in the way that STOC/FOCS are, so I like the idea of SIGACT being behind a conference of this sort.  I think it is bad for the community that, more and more, the only attendees at STOC/FOCS are people with a paper.

But I am concerned about converting STOC itself into this conference. Perceptions are slow to change so if STOC turned into the kind of conference that is outlined -- where papers are submitted and accepted rather nonselectively -- then I think there would be confusion about whether papers are "old" STOC papers (I could see people calling them "real" STOC papers, unfortunately) or "new" STOC papers.  This confusion would probably come up many times in evaluations, letters, etc.  I also worry that halving the number of (let me say it) "real" STOC/FOCS papers is not a good thing in terms of growing the field.

I haven't thought this through very carefully, but maybe a possibility would be to have a large nonselective flagship conference annually in conjunction with STOC (which would retain its usual role and name).  This could have a couple of pluses:  there would be a built-in 'seed audience' of 'key players' at the new conference (the STOC attendees), and it could help to grow STOC's visibility since it would be right there with the larger meeting (much like having STOC at FCRC sometimes does now).

Aaron Sterling


Madhu Sudan

1) I am in favor of rethinking the nature and size of STOC to serve our
community better. I am glad you are doing this.

2) I am not in favor of turning STOC into a purely social event where people
publish papers merely to justify the travel to their funding agencies.

3) I think we should rethink STOC because our community is getting larger,
with very well developed closely connected subcommunities with a few but
positive number of broadly interesting results each year. In view of
this STOC should grow, and try to support the greater volume of work, while
also trying to bring the subcommunities together.

4) I think STOC should not aim to fill a predetermined number of slots
(or number of sessions) nor should it try to needlessly restrict itself
to fixed upper bounds. It should attempt to find papers that stimulate
the program committee (which may composed as a union of subcommittees),
and then simply determine what is breadth of interest in the stimulating
papers. (Among other things I hope this will allow program committees to 
view submissions "positively" rather than "negatively".) STOC's attitude
should be similar to that in typical journals today which don't view
papers as competition to other papers, but rather it should make 
independent decisions on each paper independent of time/slot constraints.
Having done so, I don't see a need to drop standards dramatically - 
we can fix the standards (strong interest among several PC members)
and keep the number of papers variable  - I would estimate that this
might at most double the number of accepted papers (incidentally
do we have a good idea of the expected number of times a paper is submitted to
FOCS/STOC conditioned on eventual acceptance?).

5) I can imagine that coming up with a good implementation of the program
committee will be non-trivial, but should not be intractable. I am happy to
give suggestions ...

Kunal Talwar

I am generally suspicious of arguments that start with everyone-else-does-this (I guess my mom used it too many times :) ), so I came to this proposal with some skepticism. While further analysis has gotten me past the gut reaction, I still think the proposal in its current form may not be an ideal solution to whatever problem it is trying to fix.

An obvious disclaimer is that I have been part of the community for a very short period and probably have a relatively limited perspective. But I might as well share that limited perspective.

I think there are problems with FOCS/STOC and I am sure you have a list of things that people think are wrong with FOCS/STOC. So let me start with what I think is right with FOCS/STOC, so we do not throw the baby with the bathwater. Some of these positives happen to be just flip sides of the negatives, complicating the situation.

I think our community has made tremendous progress in several areas in recent years. And a lot of that progress has come not from one person hunkering down and solving problems, but from papers by different individuals that feed off each other. And this quick back-and-forth is tremendously helped by the fact that we have two conferences in a year (maybe 3 if you count soda/complexity) that we think are highly rewarding and visible outlets for our ideas; even those that we think could be developed further and lead to even better results. The deadlines for these conferences often compel us to get working to write up the ideas that exist is a vague form in our heads or on our whiteboards. Now there are some obvious drawbacks of this that I am sure you are thinking of right now (half-baked hastily written, sometimes incremental manuscripts). But it also hastens the pace of research: I like to think of these as 20 page contributions to a (very slow) polymath project. This brings in diverse perspectives, sometimes leading to better and faster final outcome than the hunker-down-in-the-basement model. Even mathematicians like Gowers are discovering the benefits of multiple-viewpoints-collaboration (in the ongoing polymath 3). In an ideal world, we would all disseminate these 20-page contributions as soon as possible through the arxiv or through our web pages or our blogs, or through a modified STOC. However in practice, people have little incentive to do so unless they are worried about being scooped.  It is hard to set up incentives for such sharing of ideas and focs/stoc miraculously do that. Removing incentives for sharing intermediate-sized works would result in more mature papers coming out of longer research programs. But there is a risk that there will be fewer final results that come out the back-and-forth,  and there may be a slowdown effect on research.

 In fact, FOCS/STOC conference pressure incentivizes us to (a) write up these results, and (b) write them up in a way that can be understood by, or at least appreciated by any one in the community. For comparison, I don't think other many communities have this latter feature.

That is related to another aspect of FOCS/STOC that I appreciate tremendously: the fact that I can go to a talk in a different subarea that I know little about, and learn something; often even learn something that I would find useful in my own research. I think these serendipitous connections are invaluable and help advance science. Our conference culture encourages outsider-friendly-dissemination (both in writing and in talks), which in turn helps these connections. These connections are the main reason I go to FOCS/STOC.

I like to think that these features (fast exchange of ideas, ease of building connections between different areas) have helped people in our area make progress not just on our own problems, but even contribute significantly on relevant questions or problems in more mature areas.

The conference culture also has some obvious problems: there exist works for which "full" versions that are carefully refereed don't exist. But I also feel this is gradually fixing itself.  As committees demand full proofs, people put out version on the arxiv once the paper is published, and as our journals get their act together and start returning reviews in reasonable timeframes, people will be more likely to send these full version to journals. Given the flux that the publishing industry is in, I wouldn't be surprised if within a decade, we (and older sciences)find a replacement that will have the benefits of journals without their negatives. But I digress.

Returning to the proposal at hand. I can think of two models for a central meeting of the community. SODA is one that many in the algorithms community feel fits that mold, but while being fairly inclusive, it stops very well short of the accept-nearly-all-reasonable-submissions model. I really enjoy SODA.
The other model, more in line with the all-reasonable-submissions proposal, is what some other communities do: I have attended INFORMS (annual), some AMS meetings (every few months), and ISMP (every 3 years). My experience at these has been the direct opposite of enjoyment (and this is even when they had several sessions in my area of interest) . I have found these events to be extremely fragmented, with a very small number of attendees at each talk. As a result, the talks and the papers are directed at the experts, and I've found that when going to a session even slightly outside my expertise (e.g. measure concentration or optimization at AMS), I struggle to understand anything; this happens less at e.g. a crypto/communication complexity talk at STOC.
Many people I have talked to about INFORMS in the past have shared their dissatisfaction with it. In fact even navigating the schedule is impossible. I find the SODA list of abstracts to be close to the limit of what I can flip through and pick from in 3 days; for INFORMS, the only option is to look at session titles and decide where you want to be; even reading the paper titles and finding a set of non-overlapping favorites would take several hours. So to some extent, I think moving to the accept-all may have the affect of fragmenting the community, rather than bringing it together. Moreover, depending on the definition of reasonable (full proofs needed?), it may also exacerbate the problem of claimed-but-detailed-proof-in-non-existent-full-version "result". Further, in the accept-all-reasonable model, submitters may have less incentive to write their submissions for anyone but the expert (since if they say it's good, it is in). I worry that the INFORMS model may reduce the cross-area interchange of ideas.

SODA is not perfect; the selection process has more randomness than one would like. But if one were to change STOC, I would strongly prefer the SODA model to the INFORMS one.

There are the other obvious negatives of changing STOC at all. An even more competitive FOCS, with much increased stakes, is probably not healthy. It may be forced to change in some unforeseen ways as a result of a drastic change in STOC. Depending on how the community reacts, there may be a decrease in the speed of dissemination, and an increase in the clique-ishness of dissemination.

Moreover, larger STOC (either model) means larger committees, which would eventually have to be partitioned into tracks, where there may not be cleanly defined balanced separators. That will also contribute to the fragmentation of a community and fewer bridges. Maybe such fragmentation is unavoidable as the community grows, but I personally would like to resist it as long as possible.

There are obvious benefits of your proposal that I will omit to avoid making this even longer. But I hope you would consider the above negatives when comparing the current proposal to other possible approaches to get some of those benefits.