tag:blogger.com,1999:blog-3722233.post112596213596678332..comments2024-03-28T14:56:46.834-05:00Comments on Computational Complexity: SODA RisingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger56125tag:blogger.com,1999:blog-3722233.post-40153255443731218332017-02-13T17:20:09.307-06:002017-02-13T17:20:09.307-06:00Correcting previous post, "16" should be...Correcting previous post, "16" should be "11"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76124198271032837302017-02-13T17:13:12.895-06:002017-02-13T17:13:12.895-06:00I did a search
https://www.google.com/search?q=sod...I did a search<br />https://www.google.com/search?q=soda+focs+stoc<br />and this was the top result.<br /><br />More than 16 years after this post was written... I would be happy to read a more up to date discussion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126536649581480932005-09-12T09:50:00.000-05:002005-09-12T09:50:00.000-05:00Re Piotr Indyk's analysis:Avrim Blum and Prabhakar...Re Piotr Indyk's analysis:<BR/><BR/>Avrim Blum and Prabhakar Raghavan wrote a paper addressing the similar question of how to "get the advantages of parallel sessions while still allowing attendees to see all the talks they wanted."<BR/><BR/>Their solution:"Have four sessions, with each talk given twice."<BR/><BR/>The analysis involves flows and expanders.<BR/><BR/><A HREF="http://www.cs.cmu.edu/~avrim/Papers/tocs.ps.gz" REL="nofollow">On a Theory of computing Symposia</A> (gzipped ps)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126504161403136982005-09-12T00:49:00.000-05:002005-09-12T00:49:00.000-05:00Dear Piotr et al. You can wrap this analysis nicel...Dear Piotr et al. You can wrap this analysis nicely and subbmit it to the comming STOC. I think that your chances are good :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126498505960073612005-09-11T23:15:00.000-05:002005-09-11T23:15:00.000-05:00- It seems to me that in scenario 1, one gets to s...- It seems to me that in scenario 1, one gets to see f*N the papers, while in scenario 2 one gets to see 3/2*f*N -1/2*N*f^2 percent of the papers.<BR/><BR/>That is correct. I think it agrees with what I wrote (although it's late, so I might have missed something). Note that I was switching between the *number* of papers/talks, and the *fraction* (of the total 1.5 f N).<BR/> <BR/>My (guarded) conclusions had to do with the fact that, it is after all, just a model (with a ^*). But it is true that scenario 2 has always higher yield than scenario 1 for f in (0,1).<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126490956091686102005-09-11T21:09:00.000-05:002005-09-11T21:09:00.000-05:00Thanks for the analysis Piotr. Is there a bug in i...Thanks for the analysis Piotr. Is there a bug in it? It seems to me that in scenario 1, one gets to see f*N the papers, while in scenario 2 one gets to see 3/2*f*N -1/2*N*f^2 percent of the papers. If so then the second number is always larger than the first, i.e. <BR/><BR/>(3/2*f*N-1/2*N*f^2) - f*N = 1/2*f*N-1/2*N*f^2 =1/2*f*N*(1-f) <BR/><BR/>which is non-negative for all values of f between 0 and 1.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126475797725940062005-09-11T16:56:00.000-05:002005-09-11T16:56:00.000-05:00This discussion is getting a little ridiculous. ...This discussion is getting a little ridiculous. Of course there are papers that are accepted by each of these conferences that have been rejected by the others: <BR/><BR/>- Papers tend to improve over time, sometimes based on the comments received when rejected. <BR/><BR/>- Changes in the expertise of between program committees even for the same conference will make somewhat different decisions. <BR/><BR/>- The competition changes.<BR/><BR/>- Probably most importantly, the sheer volume of submissions can make the decisions somewhat of a noisy process.<BR/><BR/>There is an undercurrent in this discussion that is a legitimate debating point: What is the appropriate amount of selectivity for these conferences givenn that they are unlikely to be extended beyond their 3 days of contributed papers? <BR/><BR/>Recently, SODA has had 3 parallel sessions (necessitated originally by the inclusion of many short papers, although these no longer exist), STOC has had 2 parallel sessions and FOCS has moved between parallel sessions and single sessions. FOCS has also regularly had a day of tutorials prior to the conference.<BR/><BR/>The decisions have in part been based on the conference venue; some locations simply do not permit such parallel sessions. Accommodating such sessions can restrict a conference to more expensive locations. <BR/><BR/>There is a legitimate argument that with a broad conference it is actually more important to have single sessions than at a more narrowly focused conference. Our field thrives on the tremendous cross-fertilization between sub-areas. At a more narrowly focused conference it is more likely that if one has to miss a session there will always be another one available on a not-too-distant topic. Parallel sessions at a broader conference mean that one has to choose between learning nothing about topic X or nothing about topic Y. So much of the success of our field is from the tremendous cross-fertilization between areas and this can be lost. The greater sense of community with single sessions is also an advantage.<BR/><BR/>I am not sure that I see any significant difference between 2 and 3 parallel sessions; once things are parallel a line has been crossed.<BR/><BR/>The drawback to single session conferences is also clear. It is a balancing act and I am not sure what the best approach is. In some ways it is good that we not be doctrinaire about it. <BR/><BR/>Paul BeameAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126470181062338872005-09-11T15:23:00.000-05:002005-09-11T15:23:00.000-05:00-- Apparently, its author managed to evaluate the ...-- Apparently, its author managed to evaluate the quality of 135 papers from the titles only. <BR/><BR/>All you have to do is scan for the words "complexity class" or "lower bound" or "bounded depth circuit", if absent, then the papers must be "algorithmic" and thus clearly inferior.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126469365432334872005-09-11T15:09:00.000-05:002005-09-11T15:09:00.000-05:00What about making these conferences blind review? ...<B> What about making these conferences blind review?</B> <BR/>(like other conferences for instance?) I know all the "<EM>self-thought</EM>" "<EM>big-shots</EM>" think that this is a ridiculous idea...I think the<BR/>theory community is so small that<BR/>even the program committe should not<BR/>have the right to look at the names...anyway, they are not there to find out who is writing the paper, they are there to judge the quality of the paper based on the 10 pages they have...<BR/><BR/>I think it will at least filter out the 50% or more 'useless' papers that go in just because....?<BR/><BR/>Just thinking loud ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126469258222354172005-09-11T15:07:00.000-05:002005-09-11T15:07:00.000-05:00> Now that the list of accepted papers is > out, ...> Now that the list of accepted papers is <BR/>> out, go ahead and take a look. SODA is a <BR/>> good conference, but I bet that at most<BR/>> the top 10% of papers there would be <BR/>> accepted to FOCS.<BR/><BR/>I find this remark somewhat amusing. Apparently, its author managed to evaluate the quality of 135 papers from the titles only. Surely, this should simplify the reviewing process in the future.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126447880554469642005-09-11T09:11:00.000-05:002005-09-11T09:11:00.000-05:00It is hard to make anything out of one isolated ex...It is hard to make anything out of one isolated example. For SODA, usually a single mediocre review from a p.c. member shoots you down, never mind a negative review.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126445029693006972005-09-11T08:23:00.000-05:002005-09-11T08:23:00.000-05:00STOC/FOCS might be doing a good job at picking the...STOC/FOCS might be doing a good job at picking the best papers in complexity theory.<BR/><BR/>In several other areas, they do (at best) a marginal job: partially because they lack PC expertise in these areas and partially because they get too few good submission in these areas (since people prefer to submit to the specialized conferences).<BR/><BR/>Are CG papers in STOC/FOCS better than most CG papers in SODA?<BR/>(I am from another area.)<BR/><BR/>In several cases I reviewed for STOC/FOCS, papers in my area were accepted (against my recommendation) that wouldn't have been accepted to the specialized conference.<BR/>Outside complexity, it no longer can be said that STOC/FOCS gets the best crop.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126428604482981262005-09-11T03:50:00.000-05:002005-09-11T03:50:00.000-05:00I think STOC/FOCS are much better conferences than...I think STOC/FOCS are much better conferences than SODA for another reason. I have reviewed a couple of STOC/FOCS papers and a couple of SODA papers. As a reviewer for a STOC/FOCS paper it always the case that if I said I had high confidence and gave a low score, then the paper was rejected. However, for SODA it happened once that I gave the paper a very low score--well below what should have been the acceptance threshold--along with a thorough list of the paper's weaknesses.<BR/>But the paper got in. This made me have much less respect for the SODA conference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126402453879378382005-09-10T20:34:00.000-05:002005-09-10T20:34:00.000-05:00-- SODA is a good conference, but I bet that at mo...-- SODA is a good conference, but I bet that at most the top 10% of papers there would be accepted to FOCS.<BR/><BR/>Clearly not, because FOCS/STOC is too elitist. This has advantages and disadvantages. For example, is good for the ego of people directly involved with FOCS/STOC. But it is certainly bad for the long term perspectives of these conferences, since clearly SODA is growing in size and prestige.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126401768267216312005-09-10T20:22:00.000-05:002005-09-10T20:22:00.000-05:00ask yourself whether there are really 150-200 firs...<I>ask yourself whether there are really 150-200 first tier papers per year in TCS. The right number is probably around 50, and the reason we end up publishing 200 is just so we don't accidentally miss the really good ones.</I><BR/><BR/>Even if we were to agree to this out-of-the-blue number of first tier papers (and I don't) you are assuming that all those papers go to STOC/FOCS and hence SODA simply picks up the leftovers. In practice, the papers are nowadays evenly distributed to the extent that, as indicated before, STOC and FOCS now routinely publish SODA rejects.<BR/><BR/>What is rather more interesting is that the STOC/FOCS total number of acceptances has declined slightly over the last fifteen years while the number of theoreticians has increased substantially. <BR/><BR/>Is it far fetched then to argue that with all this growth there is plenty of room for a third conference of equal (or higher) quality? Of course not! This is only jarring to those who believe that STOC/FOCS (former) higher quality is somehow a God given attribute rather than something that is acquired and nurtured through reasonable steering policies.<BR/><BR/>As Peter Shor pointed out, not growing STOC and FOCS at the proper time in the past opened the door wide open for other conferences to move in an occupy a space side-by-side to STOC and FOCS quality-wise. SODA and the specialized SoCG have now standards of quality comparable to STOC and FOCS, and many people submit interchangeably to those three, or like David, some even favor SODA over the smallish STOC and FOCS with their reduced reach.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126399288489090422005-09-10T19:41:00.000-05:002005-09-10T19:41:00.000-05:00Now that the list of accepted papers is out, go ah...Now that the list of accepted papers is out, go ahead and take a look. SODA is a good conference, but I bet that at most the top 10% of papers there would be accepted to FOCS.<BR/><BR/>For people who say that STOC/FOCS don't accept enough papers, ask yourself whether there are really 150-200 first tier papers per year in TCS. The right number is probably around 50, and the reason we end up publishing 200 is just so we don't accidentally miss the really good ones.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126311802597681582005-09-09T19:23:00.000-05:002005-09-09T19:23:00.000-05:00The list of papers accepted to SODA 2006 is availa...The list of papers accepted to SODA 2006 is <A HREF="http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509b&L=theorynt&T=0&F=&S=&P=1204" REL="nofollow">available</A> now.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126290379307488872005-09-09T13:26:00.000-05:002005-09-09T13:26:00.000-05:00A paper with errors is certainly more interesting ...A paper with errors is certainly more interesting than a trivial or incremental paper.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126287162243816622005-09-09T12:32:00.000-05:002005-09-09T12:32:00.000-05:00What about a STOC/FOCS papers with some errors? I...What about a STOC/FOCS papers with some errors? Is that also better than a SODA paper?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126209712432815742005-09-08T15:01:00.000-05:002005-09-08T15:01:00.000-05:00I know of at least two SODA rejects that were acce...<I>I know of at least two SODA rejects that were accepted in the subsequent STOC conference.</I><BR/><BR/>Add at least two accepted FOCS papers that were rejects on the corresponding SODA earlier that year.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126208247888916222005-09-08T14:37:00.000-05:002005-09-08T14:37:00.000-05:00Weird - papers rejected from FOCS routinely go to ...<I>Weird - papers rejected from FOCS routinely go to SODA, but I've never heard of SODA rejects going to STOC or FOCS. Wonder why...</I><BR/><BR/>I know of at least two SODA rejects that were accepted in the subsequent STOC conference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126204359558317972005-09-08T13:32:00.000-05:002005-09-08T13:32:00.000-05:00FOCS and STOC have stayed nearly the same size whi...FOCS and STOC have stayed nearly the same size while the theoretical computer science has grown immensely in size and splintered into several different subareas. I've been doing quantum computing for quite a while, but what was happening the last time I was paying attention was that there were just too many really good algorithms papers for FOCS and STOC to accept them all. When this happens, some of them start getting sent to SODA, and SODA gets to be a prestigious conference because all these good papers are appearing in it. <BR/><BR/>The same thing happened with the computational geometry conference earlier, although computational geometry is such a small and specialized area of computer science that most STOC and FOCS attendees didn't care that they were losing many of the best computational geometry papers. Algorithms is a central area of theory, so the best algorithms conference is a natural competitor to FOCS and STOC. <BR/><BR/>If FOCS and STOC wanted to keep the monopoly on being the best TCS conferences, they should have grown much larger and much earlier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126201721485549692005-09-08T12:48:00.000-05:002005-09-08T12:48:00.000-05:00Regarding rejected papers from SODA not being resu...Regarding rejected papers from SODA not being resubmitted to STOC/FOCS, this happens more often than one thinks. I have seen papers in fact make the rounds of all three and end up in STOC/FOCS. This is merely a function of the particular mix of submissions in a given year, and the tastes of the PC members. <BR/><BR/>It is still true that authors perceiving their results to be outstanding would submit first to STOC/FOCS. The point I think is that this is less true than it used to be, for a variety of reasons, and also because as the community grows and STOC/FOCS stay relatively fixed in size, SODA naturally receives a lot of excellent papers that can't fit in a restricted program.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126200131091164582005-09-08T12:22:00.000-05:002005-09-08T12:22:00.000-05:00I know that this kind of sentiment doesn't go over...I know that this kind of sentiment doesn't go over well in these days of dwindling NSF funding, but we are doing _theoretical_ computer science, and thus papers should have a key theoretical insight. Part of the idea of a theoretical field is to be able to think while divorced somewhat from practice. If you actually believe that theory is useful (and having seen the fruitful interaction of theorists and practioners in research labs, I do), then you shouldn't feel so strongly the need to immediately justify your theory.<BR/><BR/>I do a lot of research in algorithms, and the most painful thing I see is when a paper justifies itself on the basis of being "useful" or "practical," when often this is just a scam to sell the result. Algortihms designers _can_ do very useful stuff, with immediate results, and inspired by theory. But I believe this requires a different mindset and a different approach, which isn't as well-suited to achieving recognition in STOC/FOCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126190199992595302005-09-08T09:36:00.000-05:002005-09-08T09:36:00.000-05:00-- Weird - papers rejected from FOCS routinely go ...-- Weird - papers rejected from FOCS routinely go to SODA, but I've never heard of SODA rejects going to STOC or FOCS. Wonder why...<BR/><BR/>Easy, they don't go to FOCS because the deadlines do not line up.<BR/><BR/>Second, they are generally not sent to STOC because SODA accepts a superset of STOC/FOCS papers. The question is if this this is so because of SODA's "undeniable" lower quality as some have claimed, or because of SODA's more attuned view of what is an "important algorithmic challenge", as other posters have suggested. <BR/><BR/>This is in essence the same question that Suresh asks in his blog (paraphrasing): do STOC/FOCS prog. committees aim to select the top-k theory papers or the top-k deep/clever/pure theory papers? are they even aware of the difference?Anonymousnoreply@blogger.com