Friday, June 11, 2010

STOC/FOCS Opinion : Guest Post by Boaz Barak

Boaz Barak asked to give a guest post on the recent STOC/FOCS issue and the question of accepting more papers. So I hand the floor over to Boaz:

Do we really need more papers in STOC/FOCS?


Continuing the discussion in the STOC business meeting, I wanted to offer a somewhat opposing opinion to Lance's and Michael's view that the number of accepted papers should be significantly increased. (Since STOC and FOCS are at the moment fairly indistinguishable, the discussion below applies to both.)

In my opinion, the primary objective of a "flagship" conference such as STOC/FOCS is to highlight to researchers recent results of high quality and/or interest outside their area. We get updates on our own subfield through specialized conferences, and so the flagship conference is meant to keep the TCS community informed about progress in the entire field, and enable the transfer of ideas, techniques, problems and people across sub-fields.


An important secondary objective is to serve as a meeting place for the community, giving people in different geographic areas a chance to talk and collaborate. Why is this a secondary goal for STOC/FOCS? Because (1) opportunities to meet and collaborate can be achieved in workshops, without the tremendous effort of the refereeing process, and (2) at the moment our community has no alternative conference (or journal: I don't want to enter that debate) that performs the primary objective nearly as well as STOC/FOCS. (As an aside, people in the business meeting raised the possibility of an ICM-style meeting in TCS which sounds like a good idea to me.)


Traditionally conferences were also the primary way to make papers physically available quickly, but that has now been largely supplanted by online archives such as eccc/arxiv/eprint, and so the primary objective of refereed conferences today is indeed filtering and highlighting. But this is a very important role: without STOC/FOCS I would have only heard of papers outside my area if they were by local people, had some "buzz", or the title caught my eye- while the conference review process has its problems, it is certainly less superficial than that.


The fact that Theoretical Computer Science has grown in size and scope only makes this selection role of a flagship conference more important. Since there was no accompanying growth in our free time or attention span, I think the relevant metric is not the acceptance rate but the absolute number of papers accepted. Indeed, already STOC/FOCS together accept about 150 papers per year which is too much for anyone to follow, especially given that we need to follow specialized conferences as well.


Nevertheless, I think STOC/FOCS have on the whole been very successful, and a look at the STOC 2010  program will show some very exciting results in a variety of areas, many of which I would not have heard of otherwise. Throughout the years there were several examples of ideas and techniques transferred across areas, and rapid progress and development of other areas, that were greatly facilitated by STOC/FOCS. Program committees have always made and will always make mistakes, but the current form is still much better than having nothing at all. (E.g., I am not so naive to think my non crypto colleagues are so interested in cryptography so that even without STOC/FOCS they would go through CRYPTO/Eurocrypt/TCC proceedings to learn of the cool theory papers...)


I ignored above one more "objective" of a conference, which is to rank people in the context of hiring/promotion. The pitfalls of publication counting are well known, and here is not the place to repeat them. In any case we should not be trying to optimize our conferences for that purpose. Needless to say, accepting more papers to STOC/FOCS will not create more positions in theoretical computer science.


Are STOC/FOCS perfect? No - they could be improved in several ways. First, while the diversity of areas is perhaps unmatched by any other conference, STOC/FOCS could use better coverage in some areas (e.g., efficient cryptographic constructions, exact algorithms and hardness, and many others). Some great theory work was rejected, even multiple times, from STOC/FOCS, and some great work was never submitted. In that respect I liked a lot Dan Spielman's suggestion in the business meeting to find a way to include in STOC/FOCS great recent theory papers from other conferences. The idea of a poster session is also interesting. All talks should be videotaped and put online, so that even people who cannot make the conference (whether it's due to geography, family, or funding) can follow it. (Again, our goal should be not to maximize registration income but to maximize impact.) Personally I prefer single session rather than parallel sessions, and perhaps slightly longer talks as well, even if it means accepting a bit less papers. A pet peeve is double column papers, and page limits should be rethought now that paper proceedings seem to be on the way to extinction.

As a final note, why do I oppose adding just 10 more papers to the program? I agree this will not make much of a difference, though I think this is a change in the wrong direction. I also doubt there is any way to evaluate the effects of such a minor change. The fact that this STOC had 100 more registrants than last one demonstrates that other factors such as attractive location, strong invited talks/tutorials, and co-located conferences and workshops make much more of a difference in attendance. Perhaps SIGACT can also use some of its $800K surplus for travel support even for non student participants, and in particular people from overseas.

33 comments:

Mihai said...

Boaz, there is a healthy level of selection and an unhealthy level of selection. Let's say that the only important goal of conferences is to highlight important results. By definition, every subfield thinks it's doing something very important (otherwise, those people would move to doing something else).

Now let's say that, by some random process, some subfield C gets more influence than some subfield G. Of course people in C have a good opinion of their own work, and they honestly believe that other people should read it, so they accept more papers from that field. At the same time, less and less papers of the other field G are accepted, up to the point when those guys say "Screw it", and change their main focus to a specialized conference.

If you try to highlight too few results, you lose the audience you want to highlight them to!

I think it's healthy to highlight more results than any one person can follow, and allow for a continuum of interests. Here's one very relevant example:

1) You are a cryptographer, a field in which I have no interest. It's not that it's not an important field, but it requires too much very specialized training, and realistically I don't think I'll ever get around to doing serious work in it.

2) You can't do crypto without some level of interest in complexity (we want to prove all those assumptions one day!). So your interests overlap with the high end of complexity theory.

3) The only progress today on proving unconditional lower bounds in serious models of computation is data structure lower bounds. Of course, your interests should not go as far as this! You can say "Come back when you push the bounds to at least some high polynomial". But a complexity theorist would care both about the high-end of complexity that you need, and the low end where unconditional progress is actually happening.

4) To make progress on lower bounds, it pays to understand upper bounds :) So a person like me is interested in the data structure upper bounds, algorithms in the low end of polynomial time, etc.

These topics are way too far for any reasonable person to follow actively. Yet it's a bad idea is to draw a separation line anywhere along this continuum, and they should all appear at the same conference.

Anonymous said...

I think it is much easier to evaluate a poster session as a success or failure, or a particular venue as a success or failure, than a marginal change in the number of marginal papers accepted.

Anonymous said...

Does anyone else think that the idea of having STOC/FOCS "highlight" the best papers from "other" (i.e. "lower") conferences just reaks of snobbery?

It also costs such "chosen" authors twice as much money to present their results. If the results are so great, then maybe making STOC/FOCS more inclusive would cause these results to just be presented there in the first place ...

Anonymous said...

every subfield thinks it's doing something very important (otherwise, those people would move to doing something else).

Actually, we would be much better off if people really believed in their work. Many people simply work on what they know, with very little thought given to the import of what they study.

Anonymous said...

without STOC/FOCS I would have only heard of papers outside my area if they were by local people, had some "buzz", or the title caught my eye- while the conference review process has its problems, it is certainly less superficial than that.

It is not a valid argument as it is subjective. I hear all the times about interesting (for me) and important results, without FOCS/STOC. And on the other hand, I never take STOC/FOCS too seriously, so I don't trust such conferences to "enlighten" me on what goes on outside my area. I can just look at ECCC for instance to know what's going on in complexity.

Needless to say, accepting more papers to STOC/FOCS will not create more positions in theoretical computer science.

No, but it will extend and broaden the number of people and research areas that are accepted as important and influential in TCS. If you have a group of 50 people that regularly publish in STOC/FOCS, then (since you have succeeded in convincing enough people that STOC/FOCS are "flagship" events) the subjects they work on become artificially "more important" than those areas or research directions of people not regularly publishing there.
Limiting the number of accepted papers, while the field obviously expands, means that you deliberately and actively block and limit what it means to have "an important contribution to the field". In order to do so you have to come up with strong scientific arguments, and I do not see anyone giving such arguments.

Boaz Barak said...

Mihai: I think your example is a great illustration of the need for a "flagship" venue with very broad scope where people get a chance to hear of papers outside their area.

And indeed one can even envision a connection between cryptography and data structures (as done by this STOC paper you may have heard of :) ). (As a side note, cryptographers do care about the difference between linear and quadratic time.)

I also agree with you and Anon 6pm that it's unhealthy if the conference gets dominated by a subset of topics or people. Thus, I'd much rather accept the first paper in field G than the fifth one in field C. But I'm not sure increasing the number of papers is the best way to achieve this. Indeed, if people in area G already gave up and don't submit, then Spielman's proposal may be a better way to get the good papers in G in STOC (and as noted by Anon 4:19pm we may need to pay their travel expenses as well). Another way is to ensure the PC is sufficiently diverse and is aware of this issue. Without this the additional slots may just result in even more papers from area C.

The number of papers/talks can be more than one person can follow, but it's good for people to attend a large fraction of the talks, even in areas they don't actively follow. (And to physically enable this, I prefer single session.) To clarify I don't advocate a drastic reduction in the number of papers, but believe you can get good coverage also with 60-65 slots as well. In any case, there shouldn't be a magic number, and the PC is always free to accept more or less papers.

Anon 6pm: As I wrote, I also hear about interesting results all the time in the way you mention: attend seminars, hear from people, see interesting looking titles on archives. There are still many results I won't hear of this way. I like the fact that in addition to that, twice a year 20 people are willing to sift through 300 papers to select other results I should know about.

Anonymous said...

I am surprised about the hue and cry about flagship TCS tier-1 conferences and selectivity (when you are talking about 300 papers!). Here's some food for thought for TCS people - imagine a community larger than TCS, which has a single tier-1 conference (once a year) which accepts 25-30 papers; a field where there are no specialized "tier-1" venues. Michael knows which field I am talking about.

Anonymous said...

imagine a community larger than TCS, which has a single tier-1 conference (once a year) which accepts 25-30 papers; a field where there are no specialized "tier-1" venues. Michael knows which field I am talking about.

That's by far a better arrangement than that of TCS: because in this case the research is not dominated almost solely by one conference; i.e., one knows there is some highly prestigious conference, but still a serious researcher is not expected to publish every year a paper in this conference, since it is unreasonable by the constraints you've described. (STOC/FOCS is meant to be both a prestigious place and the standard conference for TCS.)

Anonymous said...

Finally a sensible and positive view on the current state of affairs in theoretical computer science!

This is in sharp contrast to most bloggers who will rather use their posts to channel off their personal frustration with research, generalizing things to the point where they are false, and as a result making this great community actually a less likable place (at least for those who still follow their blogs).

Thanks, Boaz, for this refreshing take.

Michael Mitzenmacher said...

Anon #9: A reminder that this blog is open to guest posts -- like this one. If you (or anyone else!) would like to write a guest post at any time that offers "sensible and positive" views, you are invited to contact me.

Anon 9 said...

Michael, my comment was not directed at you. Apparently, I'm still reading your blog.

Anonymous said...

I actually think the bar that STOC/FOCS set is too low.

As someone who has been on the PC of one of these things, I know that in a typical program, the PC readily accepts the top 30% of papers. The bottom 20% of ACCEPTED papers mostly consists of papers that nobody on the PC thinks is worth reading... even to readers who are in areas that the paper is from. To get into this bottom 20%, it is sufficient for the paper to convince people on the PC that are FROM THE AREA of the paper that the paper is a good contribution, it doesn't really have to have broad appeal. A paper that failed to make it probably didn't have a single member on the PC that was willing to stand up for it.

I would love to see STOC/FOCS accept papers from new areas, but I think the best point that Boaz makes is that our attention span/free time is not growing, and so this is what should be used to determine the size of the conference.

Boaz Barak said...

A paper that failed to make it probably didn't have a single member on the PC that was willing to stand up for it.

This is very far from my experience in STOC/FOCS PC's. I did not agree with all decisions, and thought some of the papers rejected should have got in. I believe this held for all other PC members as well. While it's true that if you fight really hard you can typically ensure a paper gets in, realistically you can only pull this off for 1-2 papers.

There is no perfect way to make these decisions, and I also never claimed the current process is best possible. It's just that I don't have ideas how to make it better. (Though perhaps getting rid of paper proceedings can help here too, by cutting the time to print, and hence enabling a longer refereeing process, with more time to get outside opinions, clarifications from authors, verify proofs, etc..)


My point was that we should not think of STOC/FOCS as handing out "prizes" but rather selecting work that the broader theory community should be aware of. One should keep in mind that quality and broader appeal are correlated, but not identical, and acceptance decision is based on some mixture of both.

Anonymous said...

My point was that we should not think of STOC/FOCS as handing out "prizes" but rather selecting work that the broader theory community should be aware of.

It's not up to STOC/FOCS, or more precisely some limited group of self-selected researchers to decide what other people "should be aware of", or what work is of "great quality". This is up to each person on his own, and in fact history and time to decide. I do not trust these people to decide for me. A serious researcher has to make up his or her own mind on what is interesting, important, etc.
This is the problem in STOC/FOCS:
on the one hand it is not like a prize (and thus people do not look at it as some sort of exotic rare honor given to someone), and on the other hand, it is not broad enough to enable healthy scientific communication, because a lot of work that interests people in the community is being banned from STOC/FOCS.

In other words, the problem is that the acceptance rate is exactly the worst possible: it's not low enough to free people from the damaging need to write a lot of STOC/FOCS papers, but it's not high enough to enable all interesting works to be a part of the canon of TCS.

Thus, one should either increase drastically the number of accepted papers; or should decrease it drastically; or should just give up the notion that STOC/FOCS represent in any way the canon of TCS.

Unknown said...

First, while the diversity of areas is perhaps unmatched by any other conference,

I disagree.

ICALP includes most STOC/FOCS topics, plus a whole track on "Logic, Semantics, Automata and Theory of Programming", topics which occur only rarely at STOC/FOCS.

I would say AAAI is arguably more diverse than STOC/FOCS.

The AAAS meeting, which is run by the publishers of the journal Science, includes topics that range from physics to geology to biochemistry.

In that respect I liked a lot Dan Spielman's suggestion in the business meeting to find a way to include in STOC/FOCS great recent theory papers from other conferences.

AAAI has a "Nectar track" that republishes works in subareas of AI not traditionally published in AAAI. We could perhaps ask someone involved with AAAI for advice on designing something similar for STOC/FOCS.

Eli Ben-Sasson said...

Hi Boaz,

First, STOC/FOCS is doing a very poor job of highlighting high quality results outside our area. Routinely, papers are not accepted because a program committee doesn't understand/care about results that are considered very important, but have the misfortune of belonging to non-trendy areas like logic, databases, automata etc.

Second, in our blogged and twittered universe one hardly needs to wait for the bi-annual 70-odd list of papers to know what's interesting in other areas.

Let me repeat my reasons for supporting an increase in the number of accepted papers, which I posted as a comment to Michael's previous post on the subject:

1. A conference is not a prize ceremony: STOC (and FOCS) has turned into one big prize ceremony. The prize is having an accepted paper. This leads to (1) a feeling of estrangement - if I don't have a paper there I don't feel like I belong there, (2) warping research - we all love prizes so now research is about STOCable papers, as many of them as possible.

2. If enough of us like it, it should be accepted: If there is a consensus in a program committee that a paper is of interest to our community, it shouldn't be rejected just because other papers are "more interesting" or deemed "better". (Have no doubt, papers are routinely rejected for exactly this reason.) If we don't impose an artificial 75 paper limit in the first place, we can really get in all the papers that we - the community at large - find interesting.

3. Few paper -> few attendees: The low attendance in STOC/FOCS is partly due to the small number of papers, which implies (1) small number of presenters, (2) small impact: out of the ~70 papers in the conference, only around 5 really matter to my current research.

A conference should be what it name suggest: A venue for people to confer, to meet, to exchange ideas, to sit leisurely and discuss research. It should strive to be a meeting attended by a large fraction of our active research community and should run for a prolonged period of time during which we'll have time to both hear interesting results and sit down and chat.

While we're at it, here's an even more radical idea: Why 2 major conferences (STOC/FOCS)? There should be one major annual theory conference as is the case in many other scientific fields. And this conference should include all good research done in the previous year, i.e., anything that enough of us would like to hear. The conference itself should be longer so that people will have time to both listen to talks and to interact, as opposed to showing up, delivering your talk and flying off.

Eli

Suresh Venkatasubramanian said...

I really like Anon11:41AM's point about the acceptance rate being in the worst possible zone. It seems that many conferences that are considered 'premier' in their field have a lower accept rate, but don't take my word for it: I'm in the process of compiling stats.

Moshe Vardi said...

As a theoretical computer scientist who has found his research area (logic and computation) essentially sidelined in STOC/FOCS, I cannot take the statement "the primary objective of a 'flagship' conference such as STOC/FOCS is to highlight to researchers recent results of high quality and/or interest outside their area" too seriously. STOC/FOCS has IS a specialized conference.

Boaz Barak said...

Moshe, Eli: As I said, I agree that a central problem with STOC/FOCS is that they do not cover all areas equally well, and they could use fewer papers from my and Eli's areas and more from Moshe's. I'm just not sure increasing the number of accepted papers is the way to solve this, since in some areas the top papers are no longer submitted to STOC/FOCS.

Eli: You say that the goal of a conference is to "confer". However, in the CS community conferences perform the service of filtering and highlighting of works that is done by journals in other fields.

Some people say that we should use journals for this role in CS as well (although then of course we'd ask how many papers should the flagship journal accept). But you seem to say that this role is no longer necessary in our "blogged and twittered universe".

I disagree: a conference refereeing process includes 300 submissions getting at least 3 reviews each, and the committee spending many hours electronically and face to face debating and trying to get to the bottom of works and their contributions. I doubt bloggers and twitterers presume to replace this process.

To summarize, I see the selection of papers in a conference as a very useful though noisy data. We should just make sure this input is not too long for us bounded-time algorithms to read...

Anonymous said...

My point was that we should not think of STOC/FOCS as handing out "prizes" but rather selecting work that the broader theory community should be aware of. One should keep in mind that quality and broader appeal are correlated, but not identical, and acceptance decision is based on some mixture of both.

This is a good distinction which is often lost to the person submitting a high-quality paper that gets rejected for lack of broad appeal, and even worse, to the hiring committees that make their decisions based on the FOCS/STOC decisions. In an ideal world, we will all think of FOCS/STOC papers as broad-appeal works and not as prizes, and hiring committees will look deeper than the number and venue of publications. In practice, neither of these is happenning anytime soon, and we should be aware of that.

One advantage of increasing the number of papers accepted is to weaken the signal so that the hiring committees are forced to look beyond this number. This would also reduce the need students may feel of maximizing the number of focs/stoc papers, which is something that sticks with them and warps all research.

So while I agree that it would be nice if FOCS/STOC had as a main goal dissemination of a few broad appeal works, in practice, they are prizes and this has consequences.

Anonymous said...

Boaz, what makes you think that people in these other communities that you propose to invite to highlight their results, would be interested in coming to present their work in FOCS/STOC?

Most people have many commitments and limited time. People would rather spend their limited time going to conferences that publish work that they are actually interested in. As FOCS/STOC no longer publishes the top results in their fields (which is why they are invited in the first place), and are rather specialized conferences, I see no reason why they would want to come. By the same logic, even if you increase the acceptance rates at FOCS/STOC, you will not gain papers from communities that have already moved on to form their own conferences.

The only thing that you might be able to do is to prevent more such communities from breaking off. I won't name any names, but for the past few years, there has been a growing feeling that algorithms is under-represented in FOCS or STOC. Perhaps raising the acceptance rate can help address this discontent.

Boaz Barak said...

To the last two anons:

The question is what is best for science. While in a specialized conferences a much larger fraction of the papers are relevant to our day to day research, if we give up the broad "flagship" conferences we reduce the chance for making unexpected connections, hearing about a new result, technique, or just a cool problem. (E.g., a nicer recent example are the new connections between the dichotomy conjecture and unique games works.) This is often the way the most significant progress is made.


These conferences are not perfect (and neither are flagship journals or conferences in other fields), but we shouldn't give up on them but rather try to see what we can do to fix the problems and make them better.
(While understanding that most works in the program will be outside our area, and that this is actually a good things.)

Anon 6:43: From my experience, hiring committees are not as shallow as you assume. When people are considering a potential colleague for the next 30 years, they take a very deep look at the work and all other relevant aspects of the candidate.

Michael Mitzenmacher said...

Boaz -- Just to go on record, I disagree with your conclusion, and indeed think your analysis actually justifies larger conferences. Pretty much I follow Mihai's point: "If you try to highlight too few results, you lose the audience you want to highlight them to!"

Or as you say: "While in a specialized conferences a much larger fraction of the papers are relevant to our day to day research, if we give up the broad "flagship" conferences we reduce the chance for making unexpected connections, hearing about a new result, technique, or just a cool problem." True enough. I'm still not clear why you think that the current number of papers, then, is enough or too big.

Your argument seems to be "150 papers is too much for me to keep up with, make the number smaller". My argument back (which seem to echo Mihai's) is that guess what, you still have to do a little work selecting papers yourself at the conferences. Yes, you have to decide which parallel session to go to, which of those papers might truly help you. The STOC/FOCS threshold shouldn't be so tight it's doing all of that selecting for you, because then effectively you're cutting off so many of the benefits that you yourself are espousing for flagship conferences. In particular, I'd argue, you're cutting off attendance. I certainly don't see how shrinking the number of papers would get more people to attend.

Boaz Barak said...

Michael:

Let me clarify that I do not strongly oppose adding 10 papers to the program, since it is indeed a small change (and already to my knowledge the PC typically has the flexibility to change the number by this amount or more).

But as a practical matter this always comes at some cost. For example, it can come at the expense of invited talks or tutorials which might be even more beneficial for increasing attendance.

I'd argue that using these 10 slots to implement Spielman's proposal might have a much more significant effect on both attendance, and (more importantly) on getting top results from a broader set of topics.

BTW If I thought that adding these 10 slots would make the difference to including top works from areas that are currently under-represented then I would support it. I'm just not at all sure this is the case.

You suggested adding 10-15 papers as a first step towards a much more significant increase in the number of papers. First, how do you measure the success? After all in this STOC we had 100 more participants without doing so. Second, a significant change in the number of papers will require a significant change in the schedule, either triple sessions or adding a day (which will likely mean cutting the well attended and well liked tutorial day).

More generally, I fear that if the number of papers grows significantly then we'll have people will only follow those works that are in their area or closely related areas. (Something that's already happenning to some extent with parallel sessions.) For example, let me ask you what would increase the probability you attend a nonzero number of crypto talks: if the conference has 3 such papers and single session, or it has 6 such papers and parallel sessions?

Michael Mitzenmacher said...

Boaz --

You state. "For example, it can come at the expense of invited talks or tutorials which might be even more beneficial for increasing attendance."

I've heard this before, but I've seen no evidence, ever, that invited talks/tutorials increase attendance at all, never mind more than adding papers. It's a nice thing, and potentially good for other reasons, but I don't accept your premise here.

"...Spielman's proposal..." I wasn't at the business meeting, but I assume this is the idea to invite papers from other top conferences to present? To be clear, this was also discussed by the EC early on as well. It's also an interesting idea, but potentially harder to implement. There are also some clear downsides -- as one commenter pointed out, the cost of having to go for those selected as just one -- that would need to be considered further. I'm not opposed to working something like this out for the future, but I'd like to see buy-in across communities.

"...First, how do you measure the success?"

More attendance than usual looking over the last 5 years. (I think we can safely count this year as something of an anomaly.) Feedback from people attending whether they noticed a difference.

Really, you could ask that question for any change. Does that mean we should never change anything, because we don't have precise measurement tools? I think we can approximately gauge user satisfaction appropriately.

"For example, let me ask you what would increase the probability you attend a nonzero number of crypto talks: if the conference has 3 such papers and single session, or it has 6 such papers and parallel sessions?"

I'll be honest -- I'm unlikely to go to a crypto talk unless I think I'll be interested in it, which means I think it's a particularly fun/exciting result, or I think it has something that will help me in my work. Otherwise, I'll sit outside and talk with people who I don't often see and benefit from talking with. It's not clear that I particularly care if the Crypto community thinks it's great in terms of getting me to go to the talk. So for me, 6 such papers greatly increases the chances there will be one that I want to see. I acknowledge that you appear to think differently, though I don't claim to truly understand why.

Anonymous said...

What Michael said. Different people have different tastes, and if there are too few papers, there is a great danger that the conference would lose its attraction to the people whose tastes are slightly different from that of the program committee.

Sanjeev Arora said...

Interesting post and comments. Couple of comments.

(a) The STOC/FOCS community is tremendously successful. I can't think of any other CS community with a conference of 300 people that routinely places several young people in the top 20 CS depts every year. (The SIGACT committee collected data on that.) We are more successful in this respect than fields with the mega conferences with thousands of attendees.

(b) There *is* a problem with fact that STOC/FOCS only accept <150 papers each year.
However, the solution is not to tamper with STOC/FOCS (don't tamper with something that works; see (a)) but to create new exciting conferences.

Each year we have several workshops in Princeton that attract 150+ people (we have one happening this week). So clearly people are willing to travel to hear interesting work. There is no reason why the community can't support another conference like STOC/FOCS.

An attempt is being made with ICS. The organizers of ICS are leading lights of STOC/FOCS community and they are trying to do something different. Lets see how that works out.

(c) Regardless of where you put the bar, you will have controversial decisions.

I admit to liking the current format of STOC/FOCS, and am reluctant to tamper with it too much.

Sanjeev Arora said...

ps Also, I think it is a lost cause to worry about the fact that STOC and FOCS no longer cover the same topics as they did 20 or 30 years ago. A STOC/FOCS person would have a hard time understanding papers in RECOMB, PODC, Eurocrypt, PODS, LICS, COLT etc. etc., even though 20-25 years ago these were all part of STOC/FOCS.

I happen to think this is a good thing. Thus although STOC/FOCS are not the sole representatives of "theoretical CS" they do seem particularly good at creating new fields of CS. I expect this trend to continue. Some new areas that it has incubated in the past decade (and which may be spun off like other areas listed above)
are: Algorithmic Game Theory, Quantum Computing, Privacy a la Dwork et al., Social network theory,...

Sanjeev Arora said...

ps Also, I think it is a lost cause to worry about the fact that STOC and FOCS no longer cover the same topics as they did 20 or 30 years ago. A STOC/FOCS person would have a hard time understanding papers in RECOMB, PODC, Eurocrypt, PODS, LICS, COLT etc. etc., even though 20-25 years ago these were all part of STOC/FOCS.

I happen to think this is a good thing. Thus although STOC/FOCS are not the sole representatives of "theoretical CS" they do seem particularly good at creating new fields of CS. I expect this trend to continue. Some new areas that it has incubated in the past decade (and which may be spun off like other areas listed above)
are: Algorithmic Game Theory, Quantum Computing, Privacy a la Dwork et al., Social network theory,...

Anonymous said...

(a) The STOC/FOCS community is tremendously successful. I can't think of any other CS community with a conference of 300 people that routinely places several young people in the top 20 CS depts every year.

(b) ... the solution is not to tamper with STOC/FOCS (don't tamper with something that works; see (a))



This argument is wrong. It just shows that the STOC/FOCS community has a lot of power. But this post is about the merits of changing STOC/FOCS for the larger community of TCS and for the benefit of TCS as a scientific discipline in itself. We are not concerned here with the benefits of the current limited STOC/FOCS community.

In fact Sanjeev's argument just strengthens the need for a change (or at least a debate about changes): because it shows the extent of influence STOC/FOCS have gained over TCS, which means that these two conferences have a lot of responsibility on their shoulders.

Jonathan Katz said...

I posted about this months ago, and got relatively little response. Briefly, I don't see why we can't have it all: accept fewer papers to STOC/FOCS (selecting based on broadest interest to the community rather than sheer technical prowess), but add on 1 or 2 days of talks on specialized topics (you could select "specialized" papers that were submitted to STOC/FOCS and were judged to be good but not of sufficiently broad interest). This would have several benefits, and would seem to satisfy all sides of the argument.

Anonymous said...

By definition, every subfield thinks it's doing something very important

You may believe your subfield is important, without believing that it is important for the rest of the TCS community to know about. You may also believe your subfield is important without believing that every paper published by your community is important.

Boaz Barak said...

Michael: I wasn't arguing that any change is impossible to measure, just that very minor changes (whose effect is likely swallowed by standard deviation in both attendance and people's enjoyment) are very hard to measure.

Jon: I like your proposal though I fear it may be too radical, and so may have unintended consequences. In particular I'd be weary of reducing too much the number of accepted papers since PC's need "buffer" both for mistakes, and for admitting papers in emerging topics that do not yet have their own home conferences (spawning off such topics is one of the success stories of STOC/FOCS).

Perhaps indeed, as some people suggested, more massive TCS co-location is the way to achieve the advantages of many of the proposals without the risk.