Finally, and most importantly, there was no discussion of the theory community's efforts to increase NSF funding for theoretical computer science, as there was at the (also beer-free) STOC business meeting. One question in particular was never asked: Are we computational geometers still even part of the theory community? The answer should be a resounding NO!, followed by a slap to the back of the head�of course computational geometry is part of theory! Look, we have big-Oh notation! Unfortunately, reality seems to disagree. None of the new material on TheoryMatters mentions computational geometry at all, although it does mention another border community: machine learning. With few exceptions, the computational geometry community rarely submits results to STOC and FOCS; this was not true ten years ago. Lots of geometric algorithms are published at STOC/FOCS by people outside the SOCG community, but nobody calls them computational geometry. (Sanjeev Arora's TSP approximation algorithms are the most glaring example.) For many years, computational geometry has been funded by a different NSF program than the rest of theoretical computer science. (This worked to our advantage when graphics was getting lots of money, but that advantage is now gone.) At one infamous SODA program committee meeting a few years ago, one PC member remarked that nobody at SODA was interested in computational geometry, they have their own conference, they should just send their results there. (This declaration led another PC member to resign.) Apparently, the divorce has been a complete success.Not just computational geometry, but the COLT (Computational Learning Theory) and the LICS (Logic in Computer Science) communities used to have their best papers in STOC/FOCS but now we see few of their papers in the standard theory conferences. As the theory community grew larger and broader, the STOC and FOCS conferences started to emphasize certain areas in theory. Those areas which were not greatly represented felt some resentment and started putting more and more emphasis on their own specialty conferences, in some cases eventually abandoning STOC and FOCS altogether.
The Conference on Computational Complexity started in 1986 as the Structure in Complexity Theory Conference (Structures) by some researchers who felt their interests of complexity were not being well represented in STOC and FOCS. This view becomes self-fulfilling—sometimes very good papers would be turned down from STOC and FOCS because they were considered a "better fit" for Structures. In response we changed the name in 1996 and brought a broader view in complexity to the conference (though not without some controversy) and tried to work our way back into the STOC/FOCS community.
Other conferences like COLT, LICS and SoCG have moved the other direction. Note that SoCG also decided not to join the Federated Conference in 2007 while both STOC and Complexity will be there. I don't expect to see COLT or LICS at FCRC either.
What can we do, if anything? STOC and FOCS cannot properly cover the broad range of areas that have ever been considered theory. Unless we have a major restructuring of how the general theory conferences operate, we will continue to shrink the vision of theory as the area continues to grow.
This comment has been removed by a blog administrator.
ReplyDeleteSTOC and FOCS cannot properly cover the broad range of areas that have ever been considered theory. Unless we have a major restructuring of how the general theory conferences operate, we will continue to shrink the vision of theory as the area continues to grow.
ReplyDeleteThis is an interesting point. I think an expansive view of theory is preferable both intelectually and in funding terms.
I'm aware that some (many?) dislike large conferences in general and FCRC in particular (viz. SoCG) and to be fair this is in part because of badly run FCRCs in the past, as well as the bad choice in location.
On the other hand most other sciences, and many fields in CS do fine with large conferences. To give an example just this week there is a conference in San Antonio on Mass Spectrometry: 300 papers, thousand or so posters, six thousand participants. Every one is there, from academic professors, to lab research scientists, to industry grunts, to manufacturers of equipment. Closer to CS, we have IJCAI (AI conference) with a thousand participants, hundreds of papers and still a ~10% acceptance ratio.
Say if FCRC is too unwieldy, how about having an FTRC, (T for Theory) and hold CC, SoCG, STOC, SPAA in a single place, at least every so many years.
The fact that STOC/FOCS has a narrower scope is not a problem, IMHO. I do have a problem, however, with the STOC/FOCS community's thinking that they represent the "Theory" community. The reality is that STOC/FOCS is right now no less specialized than, say LICS, only the pretension to generality is different.
ReplyDeleteNot only Computational Geometry, Logic, Machine Learning, but also Distributed Computing.
ReplyDeleteThese areas are treated "external" and less deserving to be accepted to STOC/FOCS (unless strong mathermatical content is present, which is not equal to an important contribution).
In all cases, strong specialized conferences were established, whose acceptance ratio is (significantly) higher than STOC's.
When this happens, researchers in these areas stop submitting to STOC/FOCS, and stop attending STOC/FOCS.
And I agree with Moshe Vardi: there is theory also outside STOC/FOCS.
I meant to write:
ReplyDelete"whose acceptance ratio is (significantly) *smaller* than STOC's
Nobody mentioned crypto, another highly theoretical area which has grown further apart from theory in recent years. Significant foundational results are still sometimes published in STOC/FOCS, but many important results now appear in CRYPTO and EUROCRYPT. In fact, a new crypto conference specializing in foundational STOC/FOCS-type results (TCC) was established recently.
ReplyDeleteThe reality is that STOC/FOCS is right now no less specialized than, say LICS, only the pretension to generality is different.
ReplyDeleteWhile at the same time, I've seen a paper rejected from FOCS with the comment "very nice and elegant result, but lots of algorithmic content [i.e. a bad thing?]. More suitable for SODA."
If STOC/FOCS wishes to remain relevant they need to embrace crypto, logic, computational geometry, algorithms, machine learning and distributed computing. Otherwise they'll slide in stature. In fact one could argue this slide has already started, as some of the recent FOCS were sparsely attended.
I agree that STOC/FOCS has become insular and there is a tendency for
ReplyDeletethe insiders to think that they are
the "true" representatives of theory and somehow that their work is not as specialized as those of other
sub-areas that have branched out.
This is unwise in the long run.
(I am an insider btw).
I believe that most of the problems
are caused by the firmly entrenched
belief in CS that conferences that
confer prestige on the selected
papers is the "right way". There
is very little incentive
to change this practice because
of tenure pressures etc. I don't
believe that this is a good model
for theoretical areas that would
benefit from quick exchange of
ideas. I have often felt that it
would be great to attend SoCG or
COLT or CRYPTO but it is difficult
to go to many conferences.
In the short term, I think a good
compromise might be to co-locate
several theory conferences once
in a while to bring the people
together.
As a side remark since most of this discussion has been about STOC/FOCS, I think the original posting was a bit unfair about SODA, and expect the remark about the PC meeting is apocryphal. This conference always has computational geometers on its program committee and this year had an invited talk and two sessions devoted to CG.
ReplyDeleteIn general, we've made an attempt to be inclusive (within the area of algorithms for discrete problems) although we're certainly not perfect.
There is a lot of issues raised by this post... I'll focus on echoing supporting the idea that theory needs larger conferences (or several co-located conference, an FTRC) bringing the community together, rather than so many small conferences and workshops. (FOCS/STOC/SODA, while on the large side, are really the minimum size we should be aiming for.) Reasons include:
ReplyDelete1) Limited travel budgets: with grants ever shrinking, there are fewer conferences I can reasonably go too. It's more cost-effective to have one big theory conference to attend and send multiple papers to.
2) Publicity: It would give theory somthing to point to, to show that we are a large and productive community. It might also (if done right) get more "non-theorists" to attend and see the wonderful things we are up to. (Lots of theory people go to networking conferences -- let's get more networking people to theory conferences!)
3) Unity: It could counteract the theory trend of increased specialization and division into smaller subgroups.
One model I like is the Allerton model, a conference covering perhaps somewhat disparate areas including networking, coding, information theory, etc. It's run by people at UIUC every year -- giving a wonderful consistency in organization. It's "small" -- these days, about 300 attendees. It generally has 6 parallel sessions in a huge variety of areas; there's always plenty of stuff I don't care about, but almost always a talk going on I want to see, and plenty of people to talk to.
Another example is INFOCOM. It's huge. It's ugly. (A common complaint is that there are a lot of less-good papers at INFOCOM, although I think that's been getting better.) But it's the place to go to see what's going on in networking.
I'd love a theory conference more like one of these. Sure, having 6 parallel sessions isn't always so great, but it gets people all in the same place, and there's something to be said for that.
Should we float the FTRC idea with ACM/SIGACT?
ReplyDeleteHal Gabow are you out there?
Say, how about FTRC 2008, with the traditional Spring theory conferences, i.e. CC, SoCG, STOC, SPAA and PODC (if they agree)?
Smaller conferences do have an advantage. I've never been to INFOCOMM, but from what I've heard I much prefer a model like Crypto where there are "only" 300-400 attendees and so it is feasible to actually meet new people.
ReplyDeleteBy the way, I don't think STOC/FOCS is insular so much because of the "insiders" (whoever they are) as because of the program committee members. Clearly, if you want CompGeom papers to get in, you need to have at least one CompGeometer on the committee. Note to the next program chair of STOC/FOCS: if you want a more diverse program, pick a more diverse program committee.
Although it might seem to be have little significance to the subject matter of the discussion, I feel that a substantial part of the problem is some kind of "race" in the community. Most of the people want a large number of publications at the cost of quality. I was going through the FOCS proceedings from early 80s and felt that there has been a substantial decline in the standards.
ReplyDeleteThis is one of the reasons why "outsiders" (courtsey Moshe Vardi) feel that they do not have a substantial share in STOC and FOCS. The problem is that there are a large number of papers in Complexity/Algorithm which are rougly of the same quality and hence it becomes difficult to distinguish. I strongly advocate that there be some element of self censorship in the theory community. This is something which we should learn from our friends in Math department. Even a mathematician of first order does not have more than 10 publications in Annals of Maths. This way we will have STOC and FOCS representing the ture status of the theory of computing.
Most importantly, I feel that the "communist" attitude of having a balance between subfields is going to take us nowhere. The sole criterion for a paper being accepted should be its quality.
I don't agree with you that there has been a decline in the quality of FOCS/STOC.
ReplyDeleteAnother interesting example is INFORMS annual meeting. INFORMS doesn't have a published proceeding or refereeing process, so presenting a paper in INFORMS doesn't have as much prestige as a FOCS paper, but it is a huge meeting (~50 parallel sessions) where everyone in the operations research & management sciences community gathers. It's very well attended, and it also provides a good place for potential employers to interview graduating students.
ReplyDeleteGiven the difficulty of making acceptance/rejection decisions when the conference is too broad, I think if we want to have occasional meetings for the entire theory community, the solution is to either go with something like FTRC, or something like INFORMS.
INFORMS doesn't have as much prestige as a FOCS paper, but it is a huge meeting (~50 parallel sessions)
ReplyDelete50 parallel sessions! How are you even supposed to read the conference program?!
I don't agree with the decline in quality from the early 80s until now, either. Also I don't think people are suggesting that a certain percentage of papers is pre-allocated to any area. What it is suggested is that PCs make the decision based solely on quality just as you suggested instead of on attitudes such as "ugh! it has logic in it, should go to LICS" or "ugh! it has geometry in it, should go to SoCG".
ReplyDeleteI think this is a consequence of the model of conferences that CS has adopted (which is not the best, in my opinion). The idea that only a small fraction of the submitted papers should be accepted is clearly excluding for large parts of the community. See the example of SoCG: only 41 papers accepted when, according to Ernie, 90 were acceptable! Why not to open concurrent sessions, and make this a better event?
ReplyDeleteFOCS/STOC also have the potential of being better, if only the community is able to be more inclusive and care less for "acceptance ratios", which is a notion that says absolutelly nothing. Having more people (working in the area) participating in a conference is more important than having strong proceedings: publication is a matter for journals.
Despite being declining, insular and narrow, STOC/FOCS is doing quite well.
ReplyDeleteIn the past few months we have heard of Reingold's L=SL, Trifonov's completely different and almost as good result, Dinur's new proof of the PCP theorem, the Khot-Vishnoi refutation of a ten years old conjecture of embeddability of L_2^2 into L_1, Morris's confirmation of a twenty years old conjecture about the Thorp shuffle, the breakthroughs in the constructions of bipartite Ramsey graphs (it's hard to tell how old were those conjectures) and the proof of the "majority is stablest" conjecture.
(Plus other things that I am surely forgetting)
Going back a few years, we see that the Annals of Mathematics has four recent papers (appeared or in press) from STOC/FOCS: primes in P, the zig-zag expanders, the Dinur-Safra hardness of vertex cover, and the paper on metric Ramsey-type theorems.
Jon Kleinberg published in the last few years one paper in Science and one in Nature related to STOC/FOCS papers (possibly more, these two are the ones that I know of).
Smoothed analysis was cited by CISE (the NSF division for all of computer science) as one of three significant discoveries in all of computer science in its 2003 budget request to congress.
This is not to deny that distributed computing, computational geometry, machine learning and other areas are not sending their best papers (or even any papers) to STOC/FOCS, that everybody loses because of that, and that we need to do something about it. Having a more diverse program committee and colocating conferences are both good ideas.
I just think that it is ridiculous to claim that STOC/FOCS is declining even while we are coming from a few years of spectacular success, or to charge that it is insular, even as the connections with mathematics, statistics, biology, physics and economics are expanding. It sounds like the joke of the Englishman who sees fog over the Channel and says "the continent is isolated."
Luca
P.S. And let's not forget about the impossibility of obfuscators, the ARV sparsest cut algorithm and its implication for other problems and for metric embeddings questions, the construction of cryptographic protocols that are impossible in the black-box model, and several other breakthroughs that I cannot recall off the top of my head.
See the example of SoCG: only 41 papers accepted when, according to Ernie, 90 were acceptable!
ReplyDeleteThis just boggles the mind.
Why not to open concurrent sessions, and make this a better event?
I think is a status quo kind of thing. A few benefit from this state of affairs, and heavily defend it.
"I think is a status quo kind of thing. A few benefit from this state of affairs"
ReplyDeleteThis is the mindset that will knock down attendence to theory conferences.
In response to some of the comments above:
ReplyDelete1) Having been to INFORMS, I think we could never get a theory conference that big-- and that's a good thing. Having attended one, I can say I found 50 parallel sessions is just too much; you really do have problems just reading the program, and finding what room to go to!
3-6 parallel sessions, in rooms close enough that you can get from one to other if you want, works quite well. FTRC -- combining 4-5 conferences, with a goal of say 500+ attendees -- would be a great idea; not too big that you can't meet new people, but big enough to be the first major theory get-together of its type that I can think of. (FCRC doesn't count, for obvious reasons.)
2) I wouldn't want to deny that theory as a whole is doing well -- I think it is. But Luca's post seems just off to me (apologies, Luca!), especially considering recent postings we've had regarding the dire funding situation in theory, and actually reinforces my "concerns" that STOC/FOCS is too narrow. Pretty much every example he cites (with the exception of Jon Kleinberg's work) is something I would have trouble explaining the importance of to non-theorists. Even the smoothed analysis results and the primes in P results, which I could easily explain, seem to be results that would apply more to mathematicians rather than computer scientists, and I don't think that's going to impress on the rest of the world the importance of theory, even if the results are very nice.
In short, I think the attitude "STOC/FOCS is healthy, just look at these results" is a point of view that risks growing the mindset among our colleagues theory is unimportant to the rest of computer science.
There isn't a contradiction here: one can be proud of all the successes of the last few months and years, and of the fact that one sees more connections between "stoc/focs theory" and mathematics, statistics, physics, economics and biology, and at the same time wish that stoc/focs were even broader.
ReplyDeleteBut I disagree on a point with Michael. One can communicate the excitement of what is going on now in theory to the average computer scientist. In fact one must do so as part of any advocacy effort. Saying "we haven't accomplished much lately, but if you give us more money we'll start doing something else" is not a winning argument either.
Also, the fact that the latest set of results makes theory more respectable in mathematics and science circles is a good thing, not a liability. Part of the bigger computer science funding crisis comes from the fact that computer science is seen from outside as a purely engineering discipline: a provider of infrastructures. So now that we have the internets, email, and windows, there are no more fundamental computer science problems to solve and we just need to produce more computers. The case that computer science is also truly a science and that it works on fundamental problems is an important case to make for all computer science, and theory should be at the core of this argument.
Arora and Chazelle wrote an op-ed that makes some of these points (I am doing a very poor job at summarizing them, while their article is very good) and it is to appear in CACM. There is also a copy on theorymatters.org under FundingCrisisLinks.
Luca
I am shocked that Michael cannot
ReplyDeleteexplain the significance of
Primes result to non-theorists
in CS. Aren't the implications to
cryptography clear? Even the SL=L result can be explained as an
algorithmic result for exploring
mazes. I agree with Luca that we
we need to convey our excitement
to outsiders. If we ourselves do
not believe in the significance
of these results the the CS field
as a whole, we have an uphill battle ahead of us.
While Lance's version of the break-off of the Structures conference (now Complexity) and LICS is correct I don't think that it is an accurate reflection of what happened in most other areas.
ReplyDeleteIn the late 1980's, the fixed single track size of STOC/FOCS and the increase in size of the community led to a situation in which only a small portion of the good work in an area would actually be accepted at STOC/FOCS because the number of papers that would fit was limited. Many areas formed their own conferences where a larger fraction of the work in their specialty could be presented. At about the same time, NSF travel budgets were cut significantly and this led to some reduction in participation in FOCS/STOC as people found more of their specialty represented in their own conferences (and to some extent could only afford to go to conferences in which they had papers.)
The spin-off conferences of the 1980's have often worked out arrangements that have convenient timing with respect to STOC/FOCS submission dates. FCRC has brought many of these spin-off conferences together and Complexity and WAW, for example, co-locate with STOC/FOCS frequently even outside of FCRC.
Computational Geometry is somewhat unusual in choosing to separate itself and very quickly directly conflict with STOC. I don't believe in any way that this is because Geometry was not well received at STOC/FOCS. Good computational geometry papers still show up at FOCS/SODA but the separation is a loss for both the Computational Geometry community and STOC/FOCS. Indeed, some of the hottest topics in recent STOC/FOCS has been in the use of the geometry of metric spaces. Surely there is no reason that computational geometry needs to be as separated as it is and there would be benefit of greater interaction.
FOCS/STOC are the premier Volume A theory conferences. They still represent that portion of theory quite broadly. I think it would be unfair to attempt to make any sharper distinction.
The situation with LICS and logic is more complicated. Unlike SOGC and most of the other 1980's spin-off conferences, LICS covers Volume B topics. Logic is certainly not excluded from STOC/FOCS - some topics have both Volume A and Volume B aspects (proof complexity, complexity of logical algorithms etc.) but the fit for STOC/FOCS is much less good for some topics. Even in the early 1980's the co-existence of Theory A and Theory B topics at FOCS/STOC was an uneasy one and it is hard to see the trend of separation between the two reversed. (The Federated Logic Conference FLoC in many ways may be Theory B's natural counterpart to
STOC/FOCS.)
The Bottom Line:
STOC/FOCS are extremely vital and active. This also means that competition to get papers into these conferences has probably never been tougher. Nonetheless Theory A reserarchers will all better off if we are not isolated in our narrow and comfortable communities but, despite the tougher odds, contribute to the broader conversation at STOC/FOCS. A huge amount of the progress in theory has been because of the tremendous cross-fertilization within our field.
Just to defend myself...
ReplyDelete1) I agree with Luca's statement that there is no contradiction -- one can be proud of the work done in the last few years while wishing STOC/FOCS was even broader. What struck me about Luca's list was how complexity-oriented it was; surely it would be nice, from my point of view, to see some more algorithmic items on the list of STOC/FOCS success stories. And they would add to the case of why theory is important to the "outside world" -- though, as Luca says, we should certainly try to trumpet these successes as well.
2) Apparently the anonymous author had a different experience with his/her colleagues after the Primes in P result than I did. Non-theorists generally fell into 2 camps. Almost everyone fell into group 1 -- they realized it was a big problem for theory and were glad we had solved it, but didn't have any idea how the result was done or why it was important. So they recognized it as a challenge, in the same manner as Fermat's Last Theorem was a challenge, and they understood the result about as much as I understand the proof of Fermat's Last Theorem.
A smaller number fell into group 2. These were either mathematicians, or mathematically trained people, who wondered why we all thought the result was such a big deal. There are faster randomized primality tests out there, so the actual impact on cryptography is not yet clear, but the feeling was it might well be nothing. (So, yes, I don't see how to explain the implications of this result in cryptography to non-theorists -- I'm not a cryptographer, so perhaps someone should explain them to me!) They weren't surprised by the result, and apparently they didn't think the result had the mathematical magnitude of something like a Fermat's last theorem.
I think explaining SL = L as a result on mazes is an interesting idea... my concern would be that such a description would lose the reasons why the result is important, from a complexity point of view, and make it seem like a "puzzle problem". But perhaps one could get across the significance to non-theorists that way.
Both results are about randomness and its role in computation. If you're describing their importance to a colleague, that is where the story should begin. Oh, and another theoretical achievement of the past 15 years--derandomization is fundamentally tied to some of our community's most compelling unsolved questions (i.e. P vs. NP, circuit lower bounds). This is an astounding and beautiful story.
ReplyDeleteThe problem with describing SL = L as a way to "solve mazes" with bounded memory is that for mazes, the "right hand rule" seems to work just fine.
Some opinions:
ReplyDelete1. There should *not* be any "inside areas" for STOC/FOCS. A paper should always be accepted only on basis of quality and not because it "belongs" to STOC/FOCS. Maybe there was such a need in the past for areas that seemed very important but simply did not have any other home. I don't think this should be the case today.
No one working in area should expect to have the "luxory" of only needing to go to STOC/FOCS to see all the interesting results.
2. Sometimes people have a more insular view of STOC/FOCS than reality. I wonder if commenters working in logic, CG, etc actually tried to send a few of their best papers to STOC/FOCS and were rejected. (One wrong rejection doesn't count - committees make mistakes all the time)
3. STOC/FOCS program chairs should be vigilant to guard against being insular and also the preception of being insular (since if you're preceived as insular you won't get the good papers, and it would do no good that you would have accepted them).
4. Don't give "theorymatters.org" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.
--boaz
Nobody would ever say "ugh! it has geometry in it, should go to SoCG" -- geometry is beautiful, one cannot be worse than indifferent to it.
ReplyDeleteAs one of the people active in
ReplyDeletetheory advocacy, I have a few comments. Pls especially see (iv).
(i) My sense was that the TCS community (interpreted broadly) is
suffering uniformly from funding problems. Furthermore, it is more united than any time I personally recall. Speaking for myself, I would be interested in having all kinds of theory (including everything mentioned here) represented at STOC/FOCS or some kind of umbrella TCS conference.
(ii) Everybody should get involved. The more diverse viewpoints are represented, the stronger our case.
Everybody should become an ambassador for TCS. Don't assume that the Karps or the Wigdersons will take care of this (though both of them are also involved).
(iii) I repeat Boaz's point: theorymatters.org is a wiki. Please contribute to it. No single person has the time to maintain it; it belongs to all of us.
(iv) Please do something that will actually have an effect. (Writing comments on a blog like this that is read only by insiders does not count.) Write a 1-2 page description of a nice TCS contribution/challenge and send it to CACM. (Or just put it on theorymatters.org, so it can be used in the ongoing TCS advocacy.) Figure out whom to lobby in Congress or the National Science Board or the CISE advisory board (your university administrations can help you with the congress part) and do it and tell the rest of us about it. Compose a form letter to your senator/congressman and distribute it to the rest of us so we can all send it to our local senators/congressmen.
(v) Random anecdote: on the mailing list associated with theorymatters,
I posted an email asking for suggestions about important challenges for TCS ---preferably phrased in language that congressmen and CISE board members can understand. Number of responses: two. (And this was in late May, after the end of spring term.)
Sanjeev
postscript:
ReplyDeleteAlso, please do not stay in a funk that the rest of TCS does not appreciate your area. Tell the rest of us about it!
Everybody is busy and loses track of what is going on outside their narrow specialty. One of the joys of my participation in TCS advocacy this spring is that I have learnt a lot about the diverse impacts of TCS. I am curious to learn more. BTW, I was the chief writer of the document on theorymatters.org (though I was a scribe for an informal group of 6-8 people).
pps: Why TCS and not "theory"?
Dick Lipton suggested this change of name. He pointed out that too many people have a negative connotation with "theory." (Think "theory of evolution.)