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.

No comments:

Post a Comment