My responses to Bill Gasarch's questions in response to reader comments about STOC and FOCS (and theory conferences more generally):
Is the community really driven by these conferences?
That depends on how you define “the community”, doesn't it. If you mean the people that regularly attend and publish in and review for FOCS and STOC, then no, they drive the conference, not the other way around. If you mean the slightly larger community of people who want to reguarly publish in STOC and FOCS—either out of real interest or pressure from hiring/tenure committees—then yes, somewhat. If you mean the even larger community of theoretical computer scientists, then no, not at all. The community members who don't fit into the STOC/FOCS subcommunity have their own venues, their own peers, their own values.
Is it bad that we are so judged?
I don't understand the question. How are we so judged?
Other fields do not have high-prestige conferences—why do we and is it a good thing?
It's neither “good” nor “bad”. It is what it is—a generally healthy but imperfect social agreement that evolved with the research community. Of course different communities have different avenues for communication.
Are the papers [at STOC and FOCS] mostly good?
Yes. Mostly. Except for the ones that aren't.
Is there a Name-School-bias? Is their a Name-person-bias? Some have suggested anonymous submissions to cure this problem.
Don't confuse correlation with causality. STOC and FOCS have a high-quality and cultural-conformity bias. People who consistently produce high quuality results that conform to community standards become Big Names. Schools that hire Big Names become Big Names themselves, so Big Name schools tend to hire and propmote Big Name people. The Big Names are the result of the quality bias, not the other way around.
In any research community, people are more willing to believe results from Big Names without reading their papers in detail than from random n00bs, sometimes unfairly so. I've seen less of this bias in the STOC/FOCS community than in other communities.
There is no problem here.
Is there an area-bias? There are several questions here: (1) is the list-of-topics on the conference annoucement leaving off important parts of theory? (2) is the committee even obeying the list as is? (3) have some areas just stopped submitting?
Who cares, no, and yes. STOC/FOCS accurately reflects a large and important subcommunity of theoretical computer scientists, but it does not cover everything, nor does it really pretend to. Most important results in computational geometry, data structures, machine learning, computational biology, logic and automata theory, and structural complexity theory are published in their own conferences (SOCG, SODA, COLT, RECOMB, LICS, Complexity) instead of STOC/FOCS, because those subfields have evolved into mature communities with their own vocabulary and culture, which most theoretical computer scientists don't understand or care about.
To be specific: Computational geometers don't submit many results to STOC/FOCS because almost nobody at STOC and FOCS goes to the computational geometry talks on purpose. STOC/FOCS attendees can be tricked into going to computational geometry talks if they don't realize that's what they are—for example, Arora's TSP approximation, Spielman and Teng's smoothed analysis, Kelner's surface circle packing—but mention Voronoi diagrams or upper envelopes or surface reconstruction and people will stay away in droves. If nobody is going to come to my talk, why should I bother submitting my work?
This is natural. Communities are defined by their mutual interests. Given limited travel budgets, nobody should be surprised that people in maturing subcommunities gravitate to their own conferences, develop their own vocabularies, and attract people who have no interest in “core” theory problems at all.
What makes the situation unhealthy is the continued belief in the STOC/FOCS community that STOC and FOCS represent all of theoretical computer science, or even the best of theoretical computer science. They don't. They represent the best of what the STOC/FOCS community has to offer, as judged by the STOC/FOCS community, but nothing more.
Is there a Hot-area-bias?
Probably. Is that bad?
Is there a mafia that controls which topics gets in?
Don't be stupid. Do you really think that anyone could control the opinions of an ever-changing programming committee? Okay, in principle, the steering committee might decide who gets to be PC chair based on their loyalty to traditional theory, and then the PC chair could select the other committee members by their reputation for loyalty to Truth, Justice, and Hardness of Approximation. The program committee could then receive its marching orders from Avi Widgerson, wringing his hands and cackling his evil cackle, deep undeground in the Kurt Gödel Memorial Orthodox Theory Lair below Einstein Drive. And then the faithful Widgersonian minions would do the bidding our their One True Enlightened Master, lest they face banishment to the intellectual hinterlands of (gasp) databases. (Dunh dunh duuuuuh.) “That's a nice thesis you have there,” Wiggy would say to each new theory PhD. “It'd be a real shame if something should happen to it. A real shame.”
Right. Have you ever tried to get fifteen academics to agree on where to eat lunch? Please.
Is there a bias towards people who can sell themselves better? To people that can write well?
I certainly hope so!
Is there a bias towards making progress on old problems rather than starting work on new problems?
If anything, I think there's a bias the other way.
Is there a bias towards novel or hard techniques?
Yes and yes, one good and one bad. The bias toward novel techniques is good; the results don't matter as much as the techniques that yield them. The comunity's preference for hard techniques, however, is misplaced; simple proofs have more impact in the long run.
Is it just random?
Of course it's "just" random! It's far from uniform, or identically distributed, or even independent, but yes, it's definitely random. Is anyone seriously suggesting that it could be anything else? (See “There is No Cabal” above.)
Are there many very good papers that do not get in? It has been suggested that we go to double sessions so that more get in. If the quality of papers has been going up over time this might make sense and would not dilute quality.
Ah, yes, the apologist's argument for grade inflation—students are better now than they used to be, so they deserve higher grades. (Also, they pay more tuition, and we need those alumni donations more.) This is usually uttered just one short breath before the ancient lament on the declining literacy, numeracy, moral fortitude, and musical taste of Kids These Days™, with the hippin and the hoppin and the bippin and the boppin.
It may very well be true that today's papers are “better” than papers published at FOCS in the 1970s, but only because the field has matured, thanks to a few giants with broad shoulders. It's not like “quality” is an absolute thing. The properties that make up a good paper are decided by the community, and the community evolves over time (or stagnates). The standards that make up good papers likewise evolve.
Yes, there are a few excellent papers that don't get in. That's to be expected; committee members are human; they disagree; they make mistakes. But much more often, there's a huge gray area of pretty good papers, some of which get in and others not, depending on the personal preferences of the committee members, the topics of other papers, the phase of the moon, the brand of coffee served at the committee meeting, and whether said coffee has already run out when a given paper is discussed.
And whadya mean "go to double sessions"? FOCS has had double sessions for years.
Is 10 pages too short for submissions? This was part of Vijay's Video Suggestion. Are figures and diagrams counted for those 10 pages? If they are they shouldn't be.
Nonsense. Of course they should be! Page limits should apply to all content, and figures and diagrams (if they're worth including at all) are definitely content. And yes, 10 pages is enough. If it really takes more than 10 pages to get the main ideas across, it's not a good conference paper and it won't make a good conference talk. Put it on the ArXiv and send it straight to a journal.
I actually like Vijay's suggestion, but not because I think theory results should be judged by presentations. The only purpose of a presentation is to inspire people to read the paper. Important details should be omitted from talks. No, I like Vijay's suggestions because it would force people to think about how they present their work when they are forced to omit all the details. Would this bias the acceptance process toward people who give good talks? Of course. Isn't that what conferences are for?
Are many submissions written at the last minute and hence badly written?
Yes. Also, many papers are written badly weeks in advance. A miniscule number of papers are written well at the last minute, too. Just not yours (or mine).
Are many submissions written by the authors taking whatever they have by the deadline and shoving it into a paper?
Yes. And sometimes these are the best papers at the conference. And sometimes they're crap.
Since the conference is about all of theory, can any committee do a good job?
Bad framing. The conference isn't about all of theory. The theoretical computer science community is too big and too diverse for a single conference. If it were, the current committees would be doing a horrible job, since they don't represent all of theory. But in fact, the committees are doing exactly what they're supposed to be doing—representing the interests of the STOC/FOCS community.
Do other conferences have these problems?
Yes. At least, to the extent that these are “problems”. Yes, other theory conferences have a bias toward quality that is misinterpreted as bias toward Big Names and/or Mafia control. (When in Tel Aviv, be sure to visit the Paul Erdös Memorial Computational Geometry Mafia Bunker And Falafel Stand. Say hi to Mickey.) Yes, other theory conferences get a lot of badly written submissions. Yes, attendees at other theory conferences tend to think they're about all research in their nominal field (comptuational geometry, say) when in fact the conference covers only a small fraction of that field.
Do you actually get that much out of the talks? If not then it is still valuable to to go for the people you meet in the hallways?
Sometimes (but not often) and yes, absolutely.
"What makes the situation unhealthy is the continued belief in the STOC/FOCS community that STOC and FOCS represent all of theoretical computer science, or even the best of theoretical computer science. They don't."
In response to the above quote, do you think there would be interest in an annual Best of Theory Conference? Authors of the best theory papers from the previous year (judged by best paper awards and/or by a program committee) could be invited to give a longer exposition of their result.
It would present a nice overview of significant recent developments in theory, their applications, and their (immediate) impact. Such a conference would probably fit best as part of FCRC but could also be held in conjunction with a major conference (not necessarily a theory conference). It could be a great venue to encourage collaborations between researchers in different sub-fields of theory and to encourage non-theoreticians to attend.
Posted by: Shripad Thite | April 22, 2007 at 03:15 AM
"What makes the situation unhealthy is the continued belief in the STOC/FOCS community that STOC and FOCS represent all of theoretical computer science, or even the best of theoretical computer science. They don't."
In response to the above quote, do you think there would be interest in an annual Best of Theory Conference? Authors of the best theory papers from the previous year (judged by best paper awards and/or by a program committee) could be invited to give a longer exposition of their result. It would present a nice overview of significant recent developments in theory, their applications, and their (immediate) impact. Such a conference would probably fit best as part of FCRC but could also be held in conjunction with a major conference (not necessarily a theory conference). It could be a great venue to encourage collaborations between researchers in different sub-fields of theory and to encourage non-theoreticians to attend.
Posted by: Shripad Thite | April 22, 2007 at 03:15 AM
Ernie - really, very good comments - I agree (say, in 99%)
Shripad - to create "Best of Theory Conference" you would need to convince these best people to attend it and with their very busy schedule I find it unlikely. In fact, you have it now - STOC and FOCS are still "Best of Theory Conferences" - they are held every half a year - so why do we need another venue?
If you want such a conference to present theory to other areas of CS then I'm not sure you need an annual conference - something like the recent NSF initiatives (Princeton and Caltech workshops) would do.
A
Posted by: A | April 22, 2007 at 08:15 AM
"In fact, you have it now - STOC and FOCS are still "Best of Theory Conferences" - they are held every half a year - so why do we need another venue?"
Um... apparently that's the 1% where we disagree. STOC and FOCS are at their best "Best of STOC/FOCS-theory conferences." But the best of computational geometry, the best of data structures, the best of learning theory, et cetera rarely if ever appear at STOC or FOCS. And most of the "best of" results at STOC and FOCS will have absolutely *no* impact on the other theory commmunities.
To answer Shripad's question... No, I don't think so. Theory is too big and too diverse for a single "best of" conference, especially when the biggest and oldest subcommunity still thinks it already has one.
Posted by: JeffE | April 22, 2007 at 09:46 AM
Hi Ernie,
Nice post ! I mostly agree with your answers. One point that I would differ on is:
"What makes the situation unhealthy is the continued belief in the STOC/FOCS community that STOC and FOCS represent all of theoretical computer science, or even the best of theoretical computer science."
I think that you don't give enough credit to S/F folks in the above. I would say that most of the "S/F regulars" that I know are very much aware of the fact that there is wonderful, high-impact theory papers that has not been published in S/F. For some examples, take, e.g., Boneh-Franklin paper on IBE; or a few Godel-prize winning papers, by Freund-Schapire, Senizergues, or, strictly speaking, even Agrawal-Kayal-Saxena.
Posted by: Piotr | April 22, 2007 at 01:30 PM
...and pardon the grammar in my previous post.
Posted by: Piotr | April 22, 2007 at 06:12 PM
Piotr: the FOCS/STOC community are likely aware that some good papers appear elsewhere, but I think many of them are under the impression that the papers that get into FOCS and STOC represent the pinnacle of their areas, that a paper that gets into STOC and FOCS would necessarily be one of the best papers at whatever other theory conference it might be sent to. And they also seem to think that if a paper does represent the best of its area, that it should get into FOCS/STOC, that the purposes of STOC/FOCS are to be representative of the best of theory generally. I don't think either is true; the differences between the papers ones sees in, on the one hand FOCS and STOC, and on the other hand SODA and SoCG seem to be much more ones of emphasis of area than of selectivity by quality.
The biggest change I would like to see in the FOCS/STOC submission process is to make hard page limits (and margin limits, and font size limits) and to firmly enforce them. The formatting may be different than for the proceedings (I'd like single column and 11pt font rather than double column 10pt) but the limits should be set as much as possible to match the total amount of content one can get in the proceedings. I'm tired of seeing papers where the authors arbitrarily decided to put a section break 1/3 of the way through, calling the first 10 pages the submission and the remaining 20 pages an appendix. They're going to have to work harder than that at condensing their results at proceedings preparation time, if they want their paper to be readable for the conference attendees; why not make them put that work in for the pc as well?
Posted by: D. Eppstein | April 22, 2007 at 10:01 PM
Hi David,
As probably intended, our two posts do not contradict each other. I am sure that there are people who believe that S/F papers are by default the best papers in their areas. Then again, I do think that most "S/F regulars" are aware of the fact that the intention of attracting best papers is realized better in some areas and worse in others.
Posted by: Piotr | April 23, 2007 at 10:26 AM
THANKS for intelligent response to my FOCS/STOC meta questions
post.
One thing- you say that `Most important results in Comp Geom,
Data Structures, Machine Learning, Comp Bio, Logic and Aut.
Theory, Complexity theory' are published in their own
conferences. That seems to cover most of theory-- whats
left to be classified as `FOCS/STOC'?
Posted by: William Gasarch | April 23, 2007 at 01:44 PM
Bill-
I am sure you would agree that most CCC publishers consider sending their stronger results to STOC/FOCS unless:
(a) the result is strong but so specialized that a non-complexity-heavy PC might turn it down
or
(b) there are time pressures and nobody wants to wait until the STOC deadline some six months after the CCC deadline
The effect this has had is that CCC gets viewed as a "little brother" conference to STOC/FOCS. This is a function of both the FOCS/STOC tastes and the considerations of the authors (time constraints and surety of acceptance versus somewhat better hiring/promotion value).
Posted by: Natrix | April 23, 2007 at 02:08 PM
I guess that the "Most important results..." statement is more true for some areas than others. I would conjecture that if you sort the list of areas in the decreasing order of probability that top result appears in a specialized conference, you would get something like:
logic & automata, comp bio, machine learning, comp geom, data structures,
complexity theory
Posted by: piotr | April 23, 2007 at 05:18 PM
This is mainly in response to David's comments.
Statistically speaking, the quality of papers in STOC/FOCS is higher than
those in SODA, and I would even venture to some extent SoCG. This is of course
a subjective opinion. People confuse the amount of technical detail and difficulty
with quality. The papers in STOC/FOCS tend to have more interesting theorem
statements and/or new technical ideas to solve open problems. Also, because the
conferences are less specialized than others, new connections between areas are
made which tend to have a lot of value. Consequently they
tend to have more impact (again statistically). And yes, STOC/FOCS wants to have
the best of theory papers from all areas. Why isn't such an ambition important
and useful for any conference, let alone conferences which want to be the premier
pan-theory conferences? Some people in the community might be arrogant but
that doesn't mean that every one is - there are plenty of wise people too and
many work in overlapping areas and submit papers to other conferences etc.
Many people who are highly respected in the STOC/FOCS community
do not actively publish there on a regular basis or even think of themselves
as STOC/FOCS people. The conference system has its quirks and STOC/FOCS is
not immune from it and cannot be but it seems strange to me that all the
ills are ascribed to the "community" as if it is a monolithic entity.
The point about page margins etc applies to other theory conferences
including SODA, SoCG etc etc. One can safely ignore the appendix if one
wants to. I don't see how the rigidity can help judge the quality of the
papers.
Posted by: | April 24, 2007 at 10:26 AM
:::: People confuse the amount of technical detail and difficulty with quality.
True and this afflicts STOC/FOCS even more than other conferences.
:::: Consequently they tend to have more impact (again statistically).
Sorry, but the available data does not back up your claim.
http://www.cs-conference-ranking.org/conferencerankings/topicsiv.html
http://citeseer.ist.psu.edu/impact.html
Posted by: | April 24, 2007 at 11:12 AM
"Statistically speaking, the quality of papers in STOC/FOCS is higher than those in SODA, and I would even venture to some extent SoCG."
I have to agree with you. But there is a vast difference between having a higher average quality and having the best papers in every area.
"The papers in STOC/FOCS tend to have more interesting theorem statements and/or new technical ideas to solve open problems."
Says you. I honestly couldn't care less about most of what STOC and FOCS publishes. (I recognize that most of the work is good; I just don't care about the topics. Just say no to PCP.) For my money, or at least for the travel lines in my grant budgets, the contents of SODA and SOCG are much more interesting, and just as full of new ideas.
"STOC/FOCS wants to have the best of theory papers from all areas. Why isn't such an ambition important and useful for any conference, let alone conferences which want to be the premier pan-theory conferences?"
There's nothing wrong with WANTING to have the best theory papers from all areas. Ambition IS important and useful for any conference. But wishing doesn't make it so. It's equally important to recognize that this goal is a goal, not a description of the current state of affairs.
As 'satellite' theory communities continue to mature and evolve, STOC and FOCS move further *away* from the goal of including the bets of every subfield.
"Some people in the community might be arrogant but
that doesn't mean that every one is - there are plenty of wise people too and many work in overlapping areas and submit papers to other conferences etc."
I never said otherwise. Unfortunately, those people seem to be in the minority.
"...it seems strange to me that all the ills are ascribed to the 'community' as if it is a monolithic entity."
I'd blame you personally if that would make you fee better, but you weren't brave enough to sign your comment. Wimp.
Conferences inherit their problems (and their strengths) from the people that make them happen—the community. Obviously. If STOC and FOCS have problems, they lie squarely at the feet of the STOC/FOCS community. I don't mean that any individual STOC/FOCS people are to blame for the problems, but I do mean that they (we?) are responsible for recognizing and addressing them. Yes, you, Mr. or Ms. Anonymous Commenter, whichever is appropriate. You.
Posted by: JeffE | April 24, 2007 at 01:16 PM
"I would conjecture that if you sort the list of areas in the decreasing order of probability that top result appears in a specialized conference, you would get something like:
logic & automata, comp bio, machine learning, comp geom, data structures, complexity theory"
You can add cryptography very near the top of the list (ahead of comp geom).
Posted by: | April 24, 2007 at 06:39 PM
"Important details should be omitted from talks. No, I like Vijay's suggestions because it would force people to think about how they present their work when they are forced to omit all the details"
Isn't it also true for the introduction of a paper? I mean, details should be omitted from the introduction and only important ideas/results should be given.
Of course, not all introductions are written this way, but this is also true for the talks.
Posted by: | April 25, 2007 at 10:08 AM