Many people believe the following:
FOCS and STOC only take technically hard results on problems that we already agree are worth studying. Papers that are truly innovative, starting new directions, have a very hard time getting into those conferences.This point or view was one of the motivations for ICS.
Is it true? If you ask someone they will give anecdotal evidence. While I don't discount that evidence, especially if it comes from people on the committee, I do wonder if there is a way to study the issue more systematically.
With this in mind I request the following:
- If you know of an innovative paper that DID make STOC or FOCS the then please leave a comment on it. Include the year the paper appeared.
- If you know of a submission that was rejected that was innovative, that the authors would not mind if it was known the paper was rejected, comment on that. Include the approx year the paper was submitted.
The paper "Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity" by Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao -- appeared in FOCS 2001. This was an innovative paper that formulated some communication complexity questions in terms of information-theoretic quantities. The results of this paper themselves aren't particularly big (as in deserving to be known broadly), but the ideas were quite innovative. As it turned out, there has been a flurry of papers building on this theme with applications to data stream complexity, quantum communication complexity, and most recently, a rather nice general theorem (Barak, Braverman, Chen, Rao) about communication complexity.
ReplyDeleteIsn't it fair to say that most innovations in our field appeared in STOC/FOCS? Few really innovative papers appeared first in other forums like journals or specialized conferences or books or anywhere else. Maybe your blog readers can also suggest innovative papers in TCS that did *not* appear in STOC/FOCS?
ReplyDeleteOr, is the question whether there have been any innovations in complexity/algorithms/TCS?
Two quickies for innovative papers in TCS that did *not*appear in FOCS/STOC (as asked by Noam):
ReplyDelete1. New Directions in Cryptography, W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, 1976.
2. Network Information Flow,
Ahlswede et al., IEEE Transactions on Information Theory,2000.
None of the Mulmuli-Sohoney approach to P vs NP ever appeared in FOCS/STOC. Even though it's obviously not done, this is currently the only reasonable approach I know of to (one of) the central problems in our field...
ReplyDeleteNoam:
ReplyDeletewell page rank paper didn't appear in stoc/focs. I'd argue that has had a major affect on theory.
nor did Kleinberg's hits paper appear in stoc/focs.
Nor did Koutsoupias/Papadumitriou paper where they coin phrase the price of anarchy ..
so no, there are major innovations in the field that didn't appear in stoc/focs
also, please take into account that a non-major paper is much likely to be considered major if is does appear in STOC/FOCS.
primes is in P
ReplyDeleteanother example to Noam's "theorem"
One paper that did appear is "Opportunistic data structures with applications" by P. Ferragina and G. Manzini. This is a paper which started the whole self-indexing field, and is not the type of paper you would typically see in FOCS (2000).
ReplyDeleteIf you know of an innovative paper that DID make STOC or FOCS the then please leave a comment on it.
ReplyDeleteWrong question Bill. You do not disprove discrimination by showing that some of X were treated fairly. You prove discrimination by showing that a disproportionate number of X got treated unfairly.
Paper reviewing is inherently noisy, and most of us wouldn't be here if we hadn't learned to handle rejection and the randomness associated with this process.
What people mean when the say that innovative papers have a hard time getting into STOC and FOCS is that the amount of noise in the review process seems to be substantially higher when it comes to innovative papers.
In my experience this extra noisiness in the reviewing process of is common across *all* conferences. However in most other conferences if a single reviewer didn't get it, your paper might still get in. Not so in STOC and FOCS where a single bad review will usually kill your paper.
Another innovative papers in TCS that did *not* appear in FOCS/STOC (as asked by Noam):
ReplyDeleteComputing on data streams. Monika Henzinger, Prabhakar Raghavan and Sridar Rajagopalan, 1998.
These examples of innovative papers that did not appear in STOC/FOCS are only interesting if the paper in question was actually submitted to STOC/FOCS in the first place.
ReplyDeleteI can't say definitively for every paper mentioned thus far, but I'm pretty sure the Diffie-Hellman paper was not submitted to STOC/FOCS. It wouldn't surprise me if the Ahlswede paper on network coding was not submitted there either.
STOC 2007: papers 1, 3, 7-19, and 31 were innovative; the rest were not.
ReplyDeleteJon is correct that it is only interesting if the paper was submitted to stoc/focs in the first place,
ReplyDeletebut note that that is not the "claim" than "noam" made: he simply said all innovative papers have been in stoc/focs, which appears to be false.
Can someone give an example of a non-innovative paper that did appear at STOC/FOCS?
ReplyDeleteNone of the Mulmuli-Sohoney approach to P vs NP even appeared in STOC/FOCS
ReplyDeleteNot entirely true: Mulmuley's STOC 1997 paper on an algebraic approach to P vs NC was closely related and a precursor to this program. That result is in some sense a key success of the program. The first paper on the program itself appeared in SIAM Journal on Computing in 2001 which meant it was probably submitted not long after the STOC paper given the lead times.
It is unclear whether a suitable description of a program like this is not going to fit well in a 10 page conference paper anyway.
Hmmm ... sample bias mechanism: "Your student has conceived two innovative research topics ... Topic A is traditionally accepted at STOC/FOCS ... Topic B is not ... which one should the student pursue?"
ReplyDeleteOver time, won't Topic A inexorably come to dominate the academic research ecosystem?
This illustrates a medical research aphorism, "The plural of anecdote is not data."
I am not sure I agree with Jonathan. I believe that realizing that outside FOCS/STOC there are lots of excellent things is already a progress with respect the present state of affairs.
ReplyDeleteAnother example:
Leslie G. Valiant: The Complexity of Computing the Permanent. Theor. Comput. Sci. (1979)
More counter examples to "noam" claim:
ReplyDeleteÉva Tardos: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3): 247-256 (1985)
"The Shannon Capacity of a Graph"
Lovasz
"Primes is in P" WAS presented at FOCS (albeit in an extra session since it was too late to be submitted to FOCS and already in press for journal publication and hence inelegible for STOC).
ReplyDeletei don't know for sure, but i heard that cook's paper on np-completeness was originally rejected or almost rejected from stoc/focs. does anyone know the details?
ReplyDeleteCook's NP-completeness paper was certainly not rejected. One tidbit I found out a few years ago is that though the definitions and consequences were in the original conference submission, the completeness of SAT was not and only appeared in the final conference version.
ReplyDeleteBTW: STOC was only in its 3rd year when the paper was published.
Primes is in P was given in the invited lecture session in focs. But the point is it went straight to a journal, so it's still a counter example to what Noam said.
ReplyDeleteThe point is, it didn't need to be a focs paper to get attention--it already had a lot of attention, and therefore was invited to a special session at focs.
There are loads of examples of great innovative STOC/FOCS papers. Some have spawned entire fields, e.g. Valiant's PAC learning paper from STOC 1984. Many have been game-changing in other ways. Noam is right, though, that this is natural given the publication outlets of the field.
ReplyDeleteThe main reason for ICS seemed to be what the rigors of STOC/FOCS review tend to require of papers that introduce some new concept. Beyond basic interest in the subject matter the review process typically tends to require that a paper whose focus is on introducing a new concept also provide some basic proof of the usefulness of that new concept.
(There are two ways that a paper can fail on the proof of concept criterion:
- No proof of concept is known or
- all the work for the proof of concept is already done in previous papers.
In the former case the paper is often viewed as premature and in the latter case there is often a discussion about whether such a paper wouldn't be better suited to a journal.)
The ICS call for papers was clear about the fact that proof of concept was not required (so that the concept introduction could be made public earlier). Some of the most intriguing papers I have read about from ICS fit that description, though they are so interesting that they would likely easily have overcome the usual STOC/FOCS hurdle on proof of concept. (There are several that had such proofs and one or two others that formalized concepts whose proof was in work already out there.)
Like all new conferences it will be interesting to see what the future holds for ICS after the initial excitement and pent-up energy. As the number of conference venues grew in the late 1980's and through the 1990's there was a fragmentation of the audience which was not always positive for the field. One positive aspect now is that despite an apparent further fragmentation of the marketplace of ideas we have tools like blogs and especially the theory blog aggregator to maintain some larger sense of community.
the review process typically tends to require that a paper whose focus is on introducing a new concept also provide some basic proof of the usefulness of that new concept.
ReplyDeleteWhen it comes to concept papers there is a tendency to ask for more than just basic proof of usefulness. Naturally a paper introducing a new concept has to provide evidence for its applicability, but from what I've seen often the bar is set much higher than that.
I seem to have annoyed many by suggesting that "most innovations in our field appeared in STOC/FOCS".... Certainly not "all".
ReplyDeleteIn any case, I'd like to classify some of the examples given into categories:
First, There are papers on the border of theory and another field. E.g., of the examples mentioned, "Network Information Flow" and the Page-Rank paper fall into this category, as do many other papers in several fields. Obviously innovative papers of this form can go into WWWC, IEEE, EC, DB confs, Econ journals, etc., according to the other field. This is good -- in fact excellent -- this is one of the key ways by which theory influences other fields.
Second, there are the papers that simply prove great results rather than "start a field". E.g. of the examples suggested so far, the "Primes in P" or min-cost circulation fall into this category. This is not what this discussion is about, and certainly there is no question that such papers would be accepted to STOC/FOCS.
Third, there are the "old" papers -- STOC/FOCS became so prominent only, say, starting in the 80s, and before that the "sociology" of the field was not so focused on conferences.
Of the examples mentioned, the types of papers that seem to fit the "innovation at FOCS/STOC" question are those:
1. Cook's theorem, which didn't really have good applications until Karp... But the community did indeed "get it" immediately.
2. Valiant's PAC paper which could be seen as not having solid content, but again the community embraced it immediately.
3. The Koutspias-Papadimitriou paper which invented PoA analysis (without the name). I am not sure whether this paper was rejected from STOC/FOCS before going to STACS, but I can well see that it would have been rejected.
4. Mulmuly's program is still an unfulfilled promise. STOC/FOCS featured the first paper in this direction and no more. Is this too much? too little? just right?
I think that from all examples that I've seen in the comments so far, the only example that, with hindsight, is a clear miss of STOC/FOCS (innovative in the sense of "opening a field"; went to another TCS outlet; last 30 years)is the PoA paper.
How about:
ReplyDeleteAlok Aggarwal, Jeffrey Scott Vitter: The I/O Complexity of Sorting and Related Problems (Extended Abstract). ICALP 1987: 467-478
which introduced the I/O model?
Valiant's recent evolvability paper did not appear in either STOC or FOCS which is rather surprising given that it was later accepted to JACM.
ReplyDeleteEven if "most innovations* appear in STOC/FOCS", isn't the relevant statistic how many times they were submitted before finally being accepted (in comparison with the more technical papers)? Just because they eventually appeared doesn't mean they had an easy time getting in.
ReplyDeleteEven this isn't the right statistic, because the paper could have improved from submission to submission. In short, I don't know a good way to measure what we want to measure.
*I assume we're talking innovations in modeling, or defining new problems, as opposed to technical innovations. Every accepted paper should somehow be innovative.
I have a 108-rejected innovative (revolutionary, really) paper [http://arxiv.org/ftp/arxiv/papers/0907/0907.3965.pdf] by STOC/FOCS and several others. But, if I am right, I hope someday it will be accepted, and then I will be famous and plentiful happy as a ClayBoy, like Mr. Perelman, and then all the painful mass hurt-rejection will well paid-up.
ReplyDelete[The ICS papers] are so interesting that they would likely easily have overcome the usual STOC/FOCS hurdle on proof of concept.
ReplyDeleteCome on, Paul, you must be joking. I certainly don't speak for the entire ICS program, but I knew about 10 papers (give or take) before the conference. They had all been rejected from STOC/FOCS/SODA --- not for being too innovative, but for being too weak.
They didn't get more interesting when they made it to ICS -- but the power of branding is amazing.
There was a really interesting discussion on John Langford's blog recently about new methods of publishing, the summary of which was basically an arxiv like forum where people could comment/discuss (but comments are only released after a critical number, say 5, to prevent bias).
ReplyDeleteThe thing that "angers" people about "noam"s assertion is that it a statement clearly meant to keep and defend things as they are, since it clearly works for him.
Instead of defending the current system, it would make sense if we also had a forward-looking discussion about future publication models. They likely will change and we would rather that it be more systematic than ad-hoc.
@Mihai: I totally agree I think I know exactly which papers are referred to.
ReplyDeleteWho is financing the conference though ?
I'd be really interested to know. Does the money come from some unknown pockets ?
About where the money comes from, the sponsors are right on the website: http://conference.itcs.tsinghua.edu.cn/ICS2010/
ReplyDeleteGood work Mihai, with taking half of Paul's sentence and contradicting it!
ReplyDeletePaul said:
Some of the most intriguing papers I have read about from ICS fit that description, though they are so interesting that they would likely easily have overcome the usual STOC/FOCS hurdle on proof of concept.
which became:
[The ICS papers] are so interesting that they would likely easily have overcome the usual STOC/FOCS hurdle on proof of concept.
Come on, Paul, you must be joking. I certainly don't speak for the entire ICS program, but I knew about 10 papers (give or take) before the conference. They had all been rejected from STOC/FOCS/SODA --- not for being too innovative, but for being too weak.
They didn't get more interesting when they made it to ICS -- but the power of branding is amazing.
Have you considered journalism as an alternate career?
@LastAnon, nice try defending a future job landing ...
ReplyDeleteI don't consider my own ICS paper to be mathematically "deep." It felt almost like performing empirical science when I was working on it, rather than pure math.
ReplyDeleteThe backstory is this: I had a conversation with Erik Winfree at a conference, about my applicaton of distribted computing techniques to self-assembly problems. He said that he thought there must be important connections between the two fields, but, on the other hand, the errors he was seeing in lab work were fundamentally different from the errors he thought distributed computing people dealt with. I went home and started reading nanoexperiment papers in depth, convinced myself that Winfree was correct, and also got a sense of the error behavior that was being observed and how it might be abstractly modeled.
I then had to define a notion of "simulation" of a molecular system by a system of distributed processors, and figure out a way to make rigorous the "new" error behavior within a distributed computing context. So I spent most of my time trying to formulate what question I even wanted to ask, and additional time trying to ask it rigorously. I spent relatively little time on mathematical gymnastics.
From Paul Beame's comment, it seems that a paper that shares characteristics with my own would be more likely to be accepted at ICS than at STOC or FOCS. That doesn't seem like a "bad" thing to me, as a field needs both new questions and new answers to old questions, and different venues could specialize in one or the other. I'm certainly glad a venue exists for new questions, though, because that is what I personally find the most interesting.
As an aside, I don't think Mihai's comment is necessarily "wrong." I didn't submit my own ICS paper to STOC or FOCS previously, so I doubt he had me in mind in his 10 or so "weak" papers, but I think there's no question that my own paper is mathematically weak relative to the bar he sets for himself. I guess the difference between him and me is that I don't see that as a problem. Conceptual advance seems more important to me than technical advance, as long as the concepts are supported with rigorous technique.
To address questions of Bill and Noam, rather than point to a specific paper, I'd like to mention that it might be more illustrative to consider entire subfields that seem shut out of STOC/FOCS, even though they have good presence in places like STACS and ICALP. Parametrized complexity and descriptive complexity come to mind. I doubt all the papers in those areas are "less innovative" than any of the STOC/FOCS papers on extractors. Not to take anything away from either STOC or FOCS, which are obviously great institutions, but anyone who thinks all innovative work appears there is a bit myopic.
Jonathan Katz said: These examples of innovative papers that did not appear in STOC/FOCS are only interesting if the paper in question was actually submitted to STOC/FOCS in the first place.
ReplyDeleteWhich can be hard to determine. But even without that information, some interesting measurement could be done. Something roughly like this: For some set of conferences including FOCS/STOC, rate how "innovative" and how technically strong each paper is. Let's say FOCS averages X% better than STACS in innovation and Y% better in technical strength. Now, is it true that X << Y? If so, that could indicate that
1. FOCS values innovation less, or
2. People tend to send innovative papers to FOCS less because they expect them to be rejected, or
3. Something else, e.g., there is just less difference in innovation across conferences (e.g., judging "innovativeness" might be a very random process).
List of Sponsors
ReplyDeleteWe sincerely thank for the following sponsors:
The Ministry of Science and Technology of the People's Republic of China
The Ministry of Education of the People's Republic of China
National Basic Research Program of China
National Natural Science Foundation of China
Tsinghua University
Institute for Theoretical Computer Science, Tsinghua University
???
ReplyDeletewhy would we want to thank money coming from an humanitarian unfriendly government ?
FREE TibET
ReplyDeleteTo 38 and the rest of yous:
ReplyDeleteMost of the papers I read have an acknowledgment of funding from the NSF.
'nuff said.
My paper "Impossibility and Universality Results for Wait-Free Synchronization." PODC 1988 was rejected (without comment) from STOC. The journal version won the Dijkstra Prize in 2003.
ReplyDeleteInterestingly enough the preliminary conceptual effort by Michael Fellows et al. on parameterized complexity was considered good enough for FOCS:
ReplyDeleteKarl R. Abrahamson, John A. Ellis, Michael R. Fellows, Manuel E. Mata: On the Complexity of Fixed Parameter Problems (Extended Abstract) FOCS 1989: 210-215 [13 citations]
but the actual full realization of the proposal jointly with Rodney Downey appeared in CCC (Structures):
Rodney G. Downey, Michael R. Fellows: Fixed-Parameter Intractability. Structure in Complexity Theory Conference 1992:36-49 [330 citations]
FOCS and STOC are American rubbish, started by arrogant Americans, for arrogant Americans. We in Europe couldn't care less about STOC/FOCS; you can keep them to yourself. Yes, I have an axe to grind. Even some Israelis hate stoc/focs. Yes, stoc/focs are american nonsense that we europeans can do without.
ReplyDelete