tag:blogger.com,1999:blog-6555947.post1747572179369592242..comments2021-01-06T23:33:11.013-07:00Comments on The Geomblog: STOC/FOCS/SODA: The Cage Match (with data!)Suresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger44125tag:blogger.com,1999:blog-6555947.post-2937863037332747022007-08-31T11:54:00.000-06:002007-08-31T11:54:00.000-06:00A fully automatic extractor would be nice to the c...A fully automatic extractor would be nice to the community (very much like EasyChair).<BR/><BR/>I guess this whole idea is from the database area, i.e., they give best paper award to the mostly referred paper at the top SIGMOD (?) conf exact 10 years ago.<BR/><BR/>With these citation statistics, maybe we can change the atmosphere a bit in the theory community. (Personally I have heard too many complains "that guy got another so-so paper into STOC".) These kind of data will certainly be useful for tenure/promotion purposes, especially for the promotion as one needs time to accumulate citations. For instance, if one only got 2 FOCS/STOC/SODA papers at the time of promotion, under the current situation, it might not be enough (people can easily say "he hasn't made enough contribution as he hasn't got many FOCS/STOC/SODA papers". But if both of the papers have high citations, then the candidate can easily list this as a fact, e.g., "both of my 2 FOCS/STOC/SODA papers were cited over 70 times and are among the top-10 mostly cited papers at that year's FOCS/STOC/SODA".<BR/><BR/>At the end of one's career, it is the 2-3 best papers which decide one's statue. Period.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-70762547008909005572007-08-31T08:19:00.000-06:002007-08-31T08:19:00.000-06:00Hi, The "grand plan" would be to exploit the know...Hi,<BR/><BR/> The "grand plan" would be to exploit the knowledge that we gained in the process, and construct a *fully automatic* extractor - then no human volunteers would be needed. Right now the Extractor utilizes a combination of automatic crawling and human help (and perhaps even some goblin magic, who knows), so it does not scale that well.<BR/><BR/>A fully automatic extractor (with low error rate) seems doable. The only problem is that it would require a fair amount of perl hacking, and so it has been relegated to the "to do" list for now. But if anyone was interested in doing this, we would be happy to provide guidelines. <BR/><BR/>Cheers,<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-18416944923945118772007-08-31T01:13:00.000-06:002007-08-31T01:13:00.000-06:00I need volunteers if I were to do this for SoCG. i...I need volunteers if I were to do this for SoCG. it was hard enough doing it for these conferences :). <BR/><BR/>also, I think SoCG is too small a community for the results to be meaningful in comparison to the "big three", so I'm not sure what the exercise would achieve.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-73512760718575178952007-08-30T22:06:00.000-06:002007-08-30T22:06:00.000-06:00Just saw this today. Very interesting.I think all ...Just saw this today. Very interesting.<BR/><BR/>I think all top theory conf should have some statistics like that.<BR/><BR/>IMHO, with these data, we should really look "# of highly ranked papers in STOC/FOCS/SODA" instead of "# of papers in STOC/FOCS/SODA".<BR/><BR/>Suresh: try to do this for SoCG, I am sure you will get lots of help.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-36075455087369396192007-08-21T14:21:00.000-06:002007-08-21T14:21:00.000-06:00Top ten papers by citation count in STOC 2003:145 ...Top ten papers by citation count in STOC 2003:<BR/><BR/>145 A tight bound on approximating arbitrary metrics by tree metrics.<BR/>95 Exponential algorithmic speedup by a quantum walk.<BR/>65 Better streaming algorithms for clustering problems.<BR/>63 Simpler and better approximation algorithms for network design.<BR/>61 Cell-probe lower bounds for the partial match problem.<BR/>54 Near-optimal network design with selfish agents.<BR/>53 Pricing network edges for heterogeneous selfish users.<BR/>52 A stochastic process on the hypercube with applications to peer-to-peer networks.<BR/>48 Optimal oblivious routing in polynomial time.<BR/>48 Hidden translation and orbit coset in quantum computing.<BR/><BR/>Top ten papers in SODA 2003:<BR/><BR/>189 Skip graphs.<BR/>162 Data streams: algorithms and applications.<BR/>101 The similarity metric.<BR/>87 Comparing top k lists.<BR/>73 Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk.<BR/>64 Packing Steiner trees.<BR/>63 An approximate truthful mechanism for combinatorial auctions with single parameter agents.<BR/>61 Computing homotopic shortest paths in the plane.<BR/>58 Dominating sets in planar graphs: branch-width and exponential speed-up.<BR/>54 High-order entropy-compressed text indexes.<BR/><BR/>From which we can clearly deduce that ... erh... SODA papers have shorter titles on the average. Any other conclusions that jump out?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-43003821949836911522007-08-02T09:24:00.000-06:002007-08-02T09:24:00.000-06:00it might also be interesting to look at how many c...it might also be interesting to look at how many citations come from papers that weren't themselves in STOC/FOCS/SODA ... how much bathwater drinking is going on? i know that at least for my own field(s), the answer is probably: a lot. you probably couldn't do this with things more recent than, say, the early 2000s, since percolation takes a while.halhttps://www.blogger.com/profile/02162908373916390369noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-88864961665474989092007-07-31T09:22:00.000-06:002007-07-31T09:22:00.000-06:00Claiming SODA 2001PiotrClaiming SODA 2001<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-84483118104919708322007-07-31T04:25:00.000-06:002007-07-31T04:25:00.000-06:00Claiming SODA 1999PiotrClaiming SODA 1999<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-30017856517776845912007-07-28T06:45:00.000-06:002007-07-28T06:45:00.000-06:00There are a number of factors in these numbers.One...There are a number of factors in these numbers.<BR/><BR/>One factor may be that the summer is when most people are not involved in courses giving them more time for research which then gets written up in time for STOC. (This is different from the "nobody is around to write things up in the summer" comment about SODA.)<BR/><BR/>Some things are just 'random'. For example, Irit Dinur's paper on the new proof of the PCP theorem, which won the best paper award at STOC 2006 and will likely be heavily cited in future, would have appeared at FOCS 2005 except for the fact that she was on the FOCS PC that year.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-10781989069002230662007-07-27T15:50:00.000-06:002007-07-27T15:50:00.000-06:00About the journal vs conference versions:1) Google...About the journal vs conference versions:<BR/><BR/>1) Google Scholar typically does collapse such papers into one entry. Thus, the Extractor did not take this into account.<BR/><BR/>2) However, the results are being currently verified and corrected by humans (see CALL FOR HELP), who take this issue into account, to the best of their abilities.<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-71356880903422535982007-07-27T15:45:00.000-06:002007-07-27T15:45:00.000-06:00Claiming STOC 1999PiotrClaiming STOC 1999<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-90246309262462473952007-07-27T14:56:00.000-06:002007-07-27T14:56:00.000-06:00When the journal version of a paper appears, peopl...When the journal version of a paper appears, people usually cites the journal version. So I am wondering if this has been taken into consideration ...<BR/><BR/>Of course, a lot of papers never have its journal versions, especially those appeared in FOCS/STOC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-59490443488547146392007-07-27T11:18:00.000-06:002007-07-27T11:18:00.000-06:00As said by someone above, Jeff's counts of the H-i...As said by someone above, Jeff's counts of the H-index, supports my theory I mentioned earlier.<BR/><BR/><I> I think the 'larger conference' argument breaks down a little when you look at the *total* number of citations to all papers per conference (over all years): SODA loses out to STOC on this measure.</I><BR/><BR/>It depends how you define "break down". I think the total number of citations for all three are pretty close; SODA is about 12% behind STOC and is 15% ahead of FOCS. These numbers aren't very significant IMHO. You could argue though that a more accurate comparison would be to take only the count of top 70 or so papers of each of these three. My guess is they won't be too far off either.Mohammad R. Salavatipourhttps://www.blogger.com/profile/18066158333139016149noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-86084135895343866462007-07-27T10:20:00.000-06:002007-07-27T10:20:00.000-06:00What I don't know is this: what is a statistically...<I>What I don't know is this: what is a statistically sound way of comparing medians that corrects for sample size ?</I><BR/><BR/>As far as I know, this is typically done using <A HREF="http://en.wikipedia.org/wiki/Bootstrapping_(statistics)" REL="nofollow">bootstrapping</A>.Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-54419680056768716452007-07-27T07:33:00.000-06:002007-07-27T07:33:00.000-06:00Anyway, it seems like it created some confusion. S...<I>Anyway, it seems like it created some confusion. Sincere apologies.</I><BR/><BR/>That explains it, good. It really made no sense otherwise. This goes to show the value of sanity checking experimental data.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-67817415165460418362007-07-27T07:31:00.000-06:002007-07-27T07:31:00.000-06:00How about the following algorithm:Look, papers 1-7...<I>How about the following algorithm:</I><BR/><BR/>Look, papers 1-70 in FOCS surely will beat papers 70-140 in SODA. SODA would have to be a conference with much higher prestige than FOCS for that not to be the case. This is something that not even the most ardent proponent of SODA has ever claimed. The claim, at least as relayed by Lance a while back, is that SODA has joined (not surpassed) STOC and FOCS as one of the big three.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-79114091538904180712007-07-27T00:39:00.000-06:002007-07-27T00:39:00.000-06:00What I don't know is this: what is a statistically...<I>What I don't know is this: what is a statistically sound way of comparing medians that corrects for sample size ? <BR/></I><BR/><BR/>How about the following algorithm:<BR/><BR/>bestchoice=median;<BR/>For (every other justfiable measure m)<BR/>{<BR/> Compare citations counts for FOCS, STOC,SODA using measure m.<BR/> If (sodaperformance[m] better than sodaperformance[bestchoice]) { bestchoice=m}<BR/>}<BR/><BR/><BR/>Next forget everything done so far and proclaim that bestchoice is a good measure of typical quality. Then compare the three conferences with respect to bestchoice, and see what results you get.Kunalhttps://www.blogger.com/profile/04248099184649099128noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-71326035899150259612007-07-26T20:50:00.000-06:002007-07-26T20:50:00.000-06:00Claiming FOCS 99.SudiptoClaiming FOCS 99.<BR/><BR/>SudiptoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-169002249506551712007-07-26T19:55:00.000-06:002007-07-26T19:55:00.000-06:00Claiming STOC 1998PiotrClaiming STOC 1998<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-59848419993034001172007-07-26T17:01:00.000-06:002007-07-26T17:01:00.000-06:00Hi, Responding to the last 3 posts about the tota...Hi,<BR/><BR/> Responding to the last 3 posts about the total number of citations: the actual numbers are:<BR/><BR/>FOCS: 20427<BR/>STOC: 26481<BR/>SODA: 23517 <BR/><BR/>These numbers were not posted anywhere earlier. I just computed them for the data available on this blog.<BR/><BR/>HOWEVER, it looks like we've got an unfortunate typo: in the table comparing our findings with Mikes, for the year 2000, there is a random phrase "over 10 years". This phrase SHOULD NOT HAVE BEEN THERE, it is a leftover from the old version of the post, and it does not make sense in the context. It will be deleted whenever Suresh comes on-line, or when I learn how to edit blog posts.<BR/><BR/>Anyway, it seems like it created some confusion. Sincere apologies. <BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-43416345131212267722007-07-26T16:33:00.000-06:002007-07-26T16:33:00.000-06:00STOC might be competing with more conferrences tha...STOC might be competing with more conferrences than FOCS. For example, STOC and SoCG deadlines are identical, and the better geometry papers are usually submitted to SoCG. Indeed, FCRC include STOC, implying that there are a big number of conferrences with similar deadlines...Sariel Har-Peledhttps://www.blogger.com/profile/00967819909489316277noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-54791802471660826102007-07-26T16:18:00.000-06:002007-07-26T16:18:00.000-06:00SODA loses out to STOC on this measure.True, but s...<I>SODA loses out to STOC on this measure.</I><BR/><BR/>True, but so does STOC to FOCS, even though STOC is larger.<BR/><BR/>I really don't understand how come STOC has less total citations than FOCS, even though they seem similar in quality and STOC has the advantage in size... the mistery deepens.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-40413859112130175002007-07-26T16:02:00.000-06:002007-07-26T16:02:00.000-06:00I think the 'larger conference' argument breaks do...I think the 'larger conference' argument breaks down a little when you look at the *total* number of citations to all papers per conference (over all years): SODA loses out to STOC on this measure.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-58582249734830619182007-07-26T15:40:00.000-06:002007-07-26T15:40:00.000-06:00Thanks for the stats, Jeff! One factor that came u...Thanks for the stats, Jeff! <BR/><BR/>One factor that came up in the context of STOC vs FOCS comparison is that, in any given year, STOC occurs a few months before FOCS (and therefore, STOC papers have more time to accumulate citations). This influences the results, at least in the short term.<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-85006666448596540032007-07-26T15:15:00.000-06:002007-07-26T15:15:00.000-06:00To me the biggest source of puzzlement is the gap ...To me the biggest source of puzzlement is the gap between STOC and FOCS citation counts, as most of us consider those conferences functionally equivalent. <BR/><BR/>Could it be due to the slightly larger number of accepted papers by STOC (about 20% more) thus echoing Mohammad R. comment on the SODA vs STOC/FOCS gap?<BR/><BR/>Or could it be due to the summer effect as suggested by anonymous 7/26/2007 12:19:00 AM? <BR/><BR/>Personally, I'm inclined towards Mohammad explanation, a larger conference almost by necessity will have somewhat weaker papers at the bottom thus dragging the citation count a bit down. Jeff's counts of the H-index, top 10 and top 25 certainly confirm this.Anonymousnoreply@blogger.com