tag:blogger.com,1999:blog-3722233.post2040122907604535952..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Do Innovative papers have a hard time getting into STOC and FOCS? I ask this objectively with no ax or teeth to grind.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger43125tag:blogger.com,1999:blog-3722233.post-38083445355112309702010-01-23T22:49:09.120-06:002010-01-23T22:49:09.120-06:00FOCS and STOC are American rubbish, started by arr...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47729764034046176282010-01-17T17:46:45.823-06:002010-01-17T17:46:45.823-06:00Interestingly enough the preliminary conceptual ef...Interestingly enough the preliminary conceptual effort by Michael Fellows et al. on parameterized complexity was considered good enough for FOCS:<br /><br />Karl 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]<br /><br />but the actual full realization of the proposal jointly with Rodney Downey appeared in CCC (Structures): <br /><br />Rodney G. Downey, Michael R. Fellows: Fixed-Parameter Intractability. Structure in Complexity Theory Conference 1992:36-49 [330 citations]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52154216755810848472010-01-17T16:02:48.887-06:002010-01-17T16:02:48.887-06:00My paper "Impossibility and Universality Resu...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.Mauricehttps://www.blogger.com/profile/03019442378581634856noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85526401133314894522010-01-17T09:23:09.561-06:002010-01-17T09:23:09.561-06:00To 38 and the rest of yous:
Most of the papers I ...To 38 and the rest of yous:<br /><br />Most of the papers I read have an acknowledgment of funding from the NSF.<br /><br />'nuff said.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-674808062616439652010-01-16T10:34:07.549-06:002010-01-16T10:34:07.549-06:00FREE TibETFREE TibETFREE TIBETnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33853380804420206842010-01-16T10:33:21.977-06:002010-01-16T10:33:21.977-06:00???
why would we want to thank money coming from...??? <br /><br />why would we want to thank money coming from an humanitarian unfriendly government ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26490242261264461822010-01-16T09:23:27.854-06:002010-01-16T09:23:27.854-06:00List of Sponsors
We sincerely thank for the follo...List of Sponsors<br /><br />We sincerely thank for the following sponsors:<br /><br />The Ministry of Science and Technology of the People's Republic of China<br /><br />The Ministry of Education of the People's Republic of China<br /><br />National Basic Research Program of China<br /><br />National Natural Science Foundation of China<br /><br />Tsinghua University<br /><br />Institute for Theoretical Computer Science, Tsinghua UniversityAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67441417297442649682010-01-15T23:17:44.327-06:002010-01-15T23:17:44.327-06:00Jonathan Katz said: These examples of innovative p...Jonathan Katz said: <i>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.</i><br /><br />Which 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<br /><br />1. FOCS values innovation less, or<br />2. People tend to send innovative papers to FOCS less because they expect them to be rejected, or<br />3. Something else, e.g., there is just less difference in innovation across conferences (e.g., judging "innovativeness" might be a very random process).Anonymoushttps://www.blogger.com/profile/13177925339061636642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31462942780944418682010-01-15T12:28:58.235-06:002010-01-15T12:28:58.235-06:00I don't consider my own ICS paper to be mathem...I 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.<br /><br />The 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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80603404296599198292010-01-15T11:38:19.668-06:002010-01-15T11:38:19.668-06:00@LastAnon, nice try defending a future job landing...@LastAnon, nice try defending a future job landing ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11263953945441356592010-01-15T11:10:59.711-06:002010-01-15T11:10:59.711-06:00Good work Mihai, with taking half of Paul's se...Good work Mihai, with taking half of Paul's sentence and contradicting it! <br /><br />Paul said:<br /><i>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.</i><br /><br />which became:<br /><i>[The ICS papers] are so interesting that they would likely easily have overcome the usual STOC/FOCS hurdle on proof of concept.<br /><br />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.<br /><br />They didn't get more interesting when they made it to ICS -- but the power of branding is amazing.</i><br /><br />Have you considered journalism as an alternate career?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85168162682995654332010-01-15T10:19:54.473-06:002010-01-15T10:19:54.473-06:00About where the money comes from, the sponsors are...About where the money comes from, the sponsors are right on the website: http://conference.itcs.tsinghua.edu.cn/ICS2010/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53688613133004566082010-01-15T09:56:13.034-06:002010-01-15T09:56:13.034-06:00@Mihai: I totally agree I think I know exactly whi...@Mihai: I totally agree I think I know exactly which papers are referred to.<br /><br />Who is financing the conference though ? <br />I'd be really interested to know. Does the money come from some unknown pockets ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7931930300035856442010-01-15T09:26:09.594-06:002010-01-15T09:26:09.594-06:00There was a really interesting discussion on John ...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).<br /><br />The 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.<br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31835248171153769602010-01-15T09:23:15.297-06:002010-01-15T09:23:15.297-06:00[The ICS papers] are so interesting that they wou...[The ICS papers] <i> are so interesting that they would likely easily have overcome the usual STOC/FOCS hurdle on proof of concept.</i><br /><br />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.<br /><br />They didn't get more interesting when they made it to ICS -- but the power of branding is amazing.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31524149788478501942010-01-15T08:11:31.527-06:002010-01-15T08:11:31.527-06:00I have a 108-rejected innovative (revolutionary, r...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.André Barbosahttp://www.andrebarbosa.eti.br/P_different_NP_Proof_Eng.htmnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68572950706222252372010-01-15T06:31:23.076-06:002010-01-15T06:31:23.076-06:00Even if "most innovations* appear in STOC/FOC...Even 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.<br /><br />Even 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.<br /><br />*I assume we're talking innovations in modeling, or defining new problems, as opposed to technical innovations. Every accepted paper should <i>somehow</i> be innovative.Znoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40585776677854728672010-01-15T01:57:54.229-06:002010-01-15T01:57:54.229-06:00Valiant's recent evolvability paper did not ap...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62727361268484565322010-01-15T00:47:05.602-06:002010-01-15T00:47:05.602-06:00How about:
Alok Aggarwal, Jeffrey Scott Vitter: T...How about:<br /><br />Alok Aggarwal, Jeffrey Scott Vitter: The I/O Complexity of Sorting and Related Problems (Extended Abstract). ICALP 1987: 467-478<br /><br />which introduced the I/O model?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57239707013375150322010-01-14T23:51:49.653-06:002010-01-14T23:51:49.653-06:00I seem to have annoyed many by suggesting that &qu...I seem to have annoyed many by suggesting that "most innovations in our field appeared in STOC/FOCS".... Certainly not "all".<br /><br />In any case, I'd like to classify some of the examples given into categories: <br /><br />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. <br /><br />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.<br /><br />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. <br /><br />Of the examples mentioned, the types of papers that seem to fit the "innovation at FOCS/STOC" question are those:<br /><br />1. Cook's theorem, which didn't really have good applications until Karp... But the community did indeed "get it" immediately.<br /><br />2. Valiant's PAC paper which could be seen as not having solid content, but again the community embraced it immediately.<br /><br />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. <br /><br />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? <br /><br />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.noamhttp://agtb.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65662944440811307152010-01-14T21:40:14.795-06:002010-01-14T21:40:14.795-06:00the review process typically tends to require that...<i>the review process typically tends to require that a paper whose focus is on introducing a new concept also provide some <b>basic</b> proof of the usefulness of that new concept.</i><br /><br />When 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6598754111644825732010-01-14T20:44:06.226-06:002010-01-14T20:44:06.226-06:00There are loads of examples of great innovative ST...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. <br /><br />The 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.<br /><br />(There are two ways that a paper can fail on the proof of concept criterion:<br />- No proof of concept is known or<br />- all the work for the proof of concept is already done in previous papers. <br />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.)<br /><br />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.) <br /> <br />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.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51980348057989328652010-01-14T18:52:05.701-06:002010-01-14T18:52:05.701-06:00Primes is in P was given in the invited lecture se...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.<br /><br />The 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17798882146467425262010-01-14T17:32:31.666-06:002010-01-14T17:32:31.666-06:00Cook's NP-completeness paper was certainly not...Cook'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.<br /><br />BTW: STOC was only in its 3rd year when the paper was published.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71626806196361355472010-01-14T17:00:11.874-06:002010-01-14T17:00:11.874-06:00i don't know for sure, but i heard that cook&#...i 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?Anonymousnoreply@blogger.com