tag:blogger.com,1999:blog-3722233.post3674710815769591763..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Time for Computer Science to Grow UpLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger119125tag:blogger.com,1999:blog-3722233.post-15163928950857630942010-08-17T12:29:45.929-05:002010-08-17T12:29:45.929-05:00Since I largely fund my own travel out of a meager...Since I largely fund my own travel out of a meager graduate student stipend, this is has led directly to money-based decisions when I send a paper to one conference over another.ali0482http://www.nrzee.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89400891142446265102009-08-27T06:12:48.966-05:002009-08-27T06:12:48.966-05:00I'm all in favor of growing up. However, befor...I'm all in favor of growing up. However, before that journals must be fixed. As others (e.g. Aspnes) said I don't understand why we write and review the papers, and then pay a publisher to read them. Also journal reviewing is broken: If I am on the PC of some conference, that at least gives me a line in my CV. Why should I do journal reviewing? Not so sure.<br /><br />So, please, fix journals before promoting them...<br /><br />// Rogerrogerhttp://www.disco.ethz.chnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65174215319638299292009-08-22T21:31:38.669-05:002009-08-22T21:31:38.669-05:00Lance, I understand your essay as arguing that con...Lance, I understand your essay as arguing that conferences cause the publish-or-perish syndrome in computer science. But all academic fields seem to suffer from it. Why blame the conference system?Benoithttps://www.blogger.com/profile/04713089900964656656noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40683427463536905812009-08-11T00:03:08.187-05:002009-08-11T00:03:08.187-05:00I'm cross-posting this comment I left at the C...I'm cross-posting this comment I left at the CACM article:<br /><br />You've described a problem that is dauntingly large and hard to solve. We can make progress by tackling pieces. <br /><br />The database community has one piece of the answer: their premier conference, VLDB, is now driven by a journal submission model (http://www.jdmr.org/). Authors submit to the journal, and a year's worth of journal submissions are presented at each year's conference. The above url links to an excellent discussion of and rationale for their procedure.<br /><br />You also highlight the way the proliferation of conferences has led to a breakdown in their value as tools for networking and drawing the community together. For these, I propose a simple solution: colocation. Take all those little conferences, and hold them all at the same time under one roof. Let them keep their independence, but share their coffeebreaks and banquets. Most importantly, allow anyone paid up at one conference to attend all of them---after all, no matter how many conferences someone "attends" at the same time, they can only consume one human-being's worth of resources. The federated computing conference does this in large, but it would be equally affective for subfields of computer science to bring together all their sub-subfields.Davidhttps://www.blogger.com/profile/04635496839285401611noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47333557693673715652009-08-06T12:12:24.334-05:002009-08-06T12:12:24.334-05:00The Computer Graphics community has moved to a mod...The Computer Graphics community has moved to a model where the best conferences have their proceedings published as a special issue of journal. For ACM SIGGRAPH (conference) and ACM Transactions on Graphics (journal) this has resulted in an increase in prestige for both. At least six other significant graphics conferences have their proceedings published as special issues of journals (Eurographics, CGI, SGP are three). Alongside this, some conferences are introducing more non-published talks, bringing back the ability to have work-in-progress presented and discussed without the need for an archival quality publication attached to the talk. ACM SIGGRAPH, for example, has so much stuff alongside the technical papers that it is quite possible to fill the entire week going to useful sessions which have no archived publication. In addition, ACM SIGGRAPH now invites the authors of the best ACM Transaction on Graphics journal papers to come and give a presentation about their journal paper. All of these ideas could be picked up by the rest of the CS community and all of them allow a gentle progression towards a better situation rather than wishing for some magic bullet solution.Neil Dodgsonhttp://www.cl.cam.ac.uk/~nad/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44881756459645576692009-08-06T08:12:08.514-05:002009-08-06T08:12:08.514-05:00One issue to consider that hasn't been raised ...One issue to consider that hasn't been raised yet -- many top conferences in CS disallow simultaneous submission of the same paper to other conferences (reasonable) and to journals (not so reasonable).<br /><br />For me, this often creates a question of conference XOR journal. <br /><br />What's the benefit of not allowing a paper to be under review at both a conference and a journal at the same time? If we're to make a transition from being a conference-centric to a journal-centric discipline, ceasing this restriction would be a good initial step.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31871875578243362202009-08-01T09:34:22.232-05:002009-08-01T09:34:22.232-05:00See also Dan Reed's "Publishing Quarks: C...See also Dan Reed's "Publishing Quarks: Considering Our Culture" at<br /> http://www.cra.org/CRN/articles/march09/Reed-Musings.htmlMoshe Vardihttps://www.blogger.com/profile/11819931416190195559noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80534077981435756612009-07-28T20:17:17.767-05:002009-07-28T20:17:17.767-05:00I thought conferences are also for the presentatio...I thought conferences are also for the presentation of papers, in addition to socialization. Anyone who has discovered something new recently should be allowed to present without a selection process that rivals college admissions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82488343782044248212009-07-28T20:14:25.758-05:002009-07-28T20:14:25.758-05:00Re "Departments would be happy to pay for tra...Re "Departments would be happy to pay for travel support": your department, maybe. Mine has no money for that sort of thing, and making a grand reorganization of CS conferences isn't likely to suddenly provide them with money.<br /><br />Especially if the trip was overseas and therefore cost that much more per attendee. You weren't assuming that CS happens only within the US, were you?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25030478298455194972009-07-28T18:35:06.486-05:002009-07-28T18:35:06.486-05:00Moving to conferences-for-socializing system would...<i>Moving to conferences-for-socializing system would probably have disparate effects on students, researchers, and faculty, and this should be taken into account. </i><br /><br />This does not have to be so. How do mathematics graduate students manage for instance ? I think if we have a annual meeting (in the style of say the winter AMS meeting) departments will be happy to provide travel support (especially since there will be only nominal registration fees). Moreover, we could have organized job fairs/interviews for faculty positions at smaller colleges at these meetings in the style of AMS meetings. So it would provide even for incentives for graduate students to attend.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71914876072288790782009-07-28T17:59:18.429-05:002009-07-28T17:59:18.429-05:00I wanted to comment on Lance's point that conf...I wanted to comment on Lance's point that conferences aren't any longer used to bring the community together, and that switching to a journal system would restore conferences to this role.<br /><br />As a graduate student, I have had many opportunities to travel to meet people at conferences where I went to present my work. If we switched to a system where we only published in journals, and conferences were used for socializing, I fear that graduate student attendance at these conferences would suffer. As a result, when the community is brought together, many graduate students would be left out.<br /><br />In the current system, a graduate student who gets a paper into a conference can usually find a way to go - perhaps from his advisor's grant, a travel award, an internship, his department, etc. (And it has not always been easy for me, and I even had to pay for some conference travel out of pocket.) I think a graduate student would have a harder time finding funding to go to a conference to "socialize."<br /><br />Moving to conferences-for-socializing system would probably have disparate effects on students, researchers, and faculty, and this should be taken into account.Lev Reyzinhttps://www.blogger.com/profile/09629175455869565423noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14064133918155092172009-07-28T11:16:56.250-05:002009-07-28T11:16:56.250-05:00Illustrations can be very helpful not only for con...<i>Illustrations can be very helpful not only for conveying information more concisely than words but for keeping the audience awake.<br /></i><br /><br />This idea that its the speaker's responsibility to keep the audience awake and entertained (and might be to slip in some useful scientific tidbits in between that the audience members can sub-consciously absorb) encapsulates much that is wrong in our community. <br /><br />It is the primary responsibility of the speaker to give a clear talk with legible and organized blackboard work (or transperencies if that is the case). But it is also the responsiility of the people in the audience to pay utmost attention and to think; and not expect entertainment or sound-bites. A scientific talk is not a sit-com.<br /><br />This undue expectation of being entertained on every occasion has seeped into our classrooms and in our textbooks, diluting content and leading to a point where students (I am talking about US undergraduates mostly here) expect to be entertained more than being lectured to. The results are there for all to see.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61427352853398022312009-07-28T10:48:13.286-05:002009-07-28T10:48:13.286-05:00Carter, simple and trivial are two different thing...Carter, simple and trivial are two different things. The algorithm in KT was perhaps not known in the economics literature. Given the existing work in CS and ORabout flows, the algorithm could be given as an excercise in an advanced grad class.<br /><br />The economics part is what anonymous are disputing here. One thing to note is that this paper is still better than many others in AGT. In those papers you could feel an intentional spin.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48940712356665489572009-07-28T10:31:52.475-05:002009-07-28T10:31:52.475-05:00To #105: conference talks may be serious business ...To #105: conference talks may be serious business but that doesn't imply that they ought to be boring. I find your rejection of pictures alarming — illustrations can be very helpful not only for conveying information more concisely than words but for keeping the audience awake. Even clip art can help in differentiating the slides from each other and keeping them memorable, so that the audience can better remember later in the talk what happened earlier. My preference would be to have a picture of some sort on every slide of a talk, although my talks usually don't quite reach that standard.<br /><br />Re: <i>One should understand that giving a scientific talk is a serious business (almost as serious as writing a paper), and the limited time should be used very judiciously to transmit as much information as possible.</i>: no. This attitude leads to horrible unlistenable talks in which the authors goes on and on about the minutiae of his or her paper and the slides are full of unreadable tiny print. One should carefully edit down the content to a suitable subset of highlights that will convey the nature of the talk, and lead interested audience members to go read the proceedings if they want to find out the details. Too little is better than too much.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63630067510795235372009-07-28T08:16:20.892-05:002009-07-28T08:16:20.892-05:00Paul Beame wrote:
"I hesitate to emulate math...Paul Beame wrote:<br />"I hesitate to emulate math conferences on another level: while there are many good expositors in math, why are there so many math talks in which the authors print out sections of their papers on slides and proceeded to read from them?"<br /><br /><br />While this may be so (but this is changing with growing use of the latex package beamer), 90% of TCS talks are devalued and rendered contentless by meaningless pictures/animation, as well as attempts at stupid humor/lame jokes etc. One should understand that giving a scientific talk is a serious business (almost as serious as writing a paper), and the limited time should be used very judiciously to transmit as much information as possible. Mathematicians often take this advice too literally, but CS talks often go the other way and become frivolous and devoid of scientific contents for the most parts.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28271295355804625312009-07-28T05:28:38.450-05:002009-07-28T05:28:38.450-05:00Much of the discussion has focused on TCS (algorit...Much of the discussion has focused on TCS (algorithms, complexity, semantics etc) and ignored that Lance's original claim was about ALL of CS. Similarly comments on the Snyder et al CRA report ignore that it was specifically limited to "experimental CS" (eg OS, DB, networking, architecture...). Throughout any discussion on conferences, journals, research ranking, job prospects etc, we all need to realize that different fields within CS work very differently. I urge theory people to look at descriptions of the top systems conferences eg http://matt-welsh.blogspot.com/2009/07/sensys-2009-pc-meeting.html to see an alternative model from FOCS/STOC that is also not like Math, Physics or other old fields!Alan Feketenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4311180078578614922009-07-28T03:26:46.665-05:002009-07-28T03:26:46.665-05:00"I think the flow is pretty much in one direc..."I think the flow is pretty much in one direction. I am yet to see any techniques originating in TCS meaningfully impact research in additive combinatorics (other than nuggets in the intro citing so called "applications" in another "applied" field (i.e. TCS))."<br /><br />The "quadratic" Gowers inverse theorem was proved independently by both Samorodnitsky and Green+Tao. Samorodnitsky's theorem works for functions over even characteristic, whereas Green and Tao's version works over odd characteristic. Both proofs follow Gowers' approach and so bear the same structural outline. Both versions have applications in their respective field, the former in constructing PCPs (a followup work with Trevisan), and the latter in obtaining stronger bounds for Szemeredi's Theorem of length 4. However, neither calculation seems to work if one switches the parity of the field's characteristic.<br /><br />Subsequently, the "cubic" Gowers inverse conjecture (over finite fields of low char) was again independently shown to be false by Lovett+Meshulam+Samorodnitsky, and Green+Tao. In fact, key steps in that paper by G+T use a lemma by Bogdanov+Viola (Tao has a blog post on this) and a neat Ramsey-styled argument from Alon+Beigel's CCC paper. L+M+S gave a stronger bound in measuring the "dis-correlation" of S_4 with cubics, though G+T's argument may be easier to visualize.<br /><br />As a previous commenter noted, Dvir's short proof of the Kakeya conjecture over finite fields uses the "polynomial method" in extremal combinatorics, which is frequently used in complexity and coding.<br /><br />Consider also (dense) graph property testing. While Szemeredi's regularity lemma already implies several corollaries about graph testing, many papers since 2000 have made more progress and develop new techniques.<br /><br />As an application, consider the "arithmetic regularity lemma" paper by Green. He conjectured a particular form of a removal-type lemma holds for function. As a special case, he proved via Fourier analysis a "triangle-removal lemma" for functions. Last year, Kral, Serra, and Vena, using a particular form of Szemeredi's regularity lemma developed in property testing, gave an non-Fourier-based proof of Green's triangle removal lemma. Since the proof is non-Fourier, their work generalizes to settings with more flavor. Building on their techniques, both K+S+V (in a followup work) and Shapira, in independent papers, resolved Green's conjecture affirmatively. Though I haven't parsed through their proofs, they do seem to rely on perspectives from both additive combinatorics and property testing. <br /><br />Victor ChenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69921643850189674112009-07-28T03:15:58.559-05:002009-07-28T03:15:58.559-05:00I would be very interested in having the anonymous...I would be very interested in having the anonymous commenter re the K-T paper substantiate with references to book chapters or articles currently available online or at a university library.<br /><br />Having spent a good amount of time analyzing the computational complexity of related problems, I find it hard to believe that the econ theoretic techniques, however simple they are after the fact, are obvious to apply to the K-T collaboration problem unless indicated with the problem set obviousness of "use technique A to solve problem Y". <br /><br />Simpler techniques to solve a problem can be better for many reasons, but that doesn't mean they are apriori obvious.carter t schonwaldhttps://www.blogger.com/profile/16546056304179288828noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70768522669911605752009-07-28T01:37:12.039-05:002009-07-28T01:37:12.039-05:00To answer Mark Wilson's question of "why ...To answer Mark Wilson's question of "why not the math model?": <br /><br />(1) Speed: <i> arXiv (why are there so few CS papers there?)</i><br /><br />This is largely historical. For quantum, computational geometry, and crypto the arxiv is very active. For complexity there has been an alternative ePrint server (ECCC) and in the algorithms and complexity areas the arxiv was initially dominated by work that was peripheral to the field and crap submitted by people who didn't know what they were talking about. This inhibited people with good papers from submitting there. This may change and certainly the arxiv is a good model for speed (though certainly not for its user interface for readers) - I said as much in my earlier comment. <br /><br />(2) Selection:<br /><i>invited addresses, workshops, special sessions, prizes, Mathematical Reviews, blogs (in particular, why is Computing Reviews so little used in CS?)</i><br /><br />The very jumbled nature of this suggestion shows why it doesn't cut it. We already have workshops in addition to conferences but they only help a small minority who can attend them. We have a few invited talks but this is hardly enough to cover the speed and directions in which the field is moving. The typical math conference has one to two plenary invited talks per day (still too few to highlight the new directions since they are often designed to showcase stars rather than simply the best recent work - though the two often go together), a number of sessions in which organizers invite their friends or people whose work they know, and a collection of other contributed papers with wide variation in quality. <br /><br />My experience has been that the most interesting parts are in the invited talks and organized sessions but they don't do much of a job at highlighting the range of the best new work. (I hesitate to emulate math conferences on another level: while there are many good expositors in math, why are there so many math talks in which the authors print out sections of their papers on slides and proceeded to read from them?)<br /> <br />As for Computing Reviews - when you have something of low quality it tends to keep the good work away. To all intents this died out in the 1980's. The level of diversity of all of CS is an order of magnitude greater than in mathematics, which makes the Reviews model unworkable. It is a fairly slow process, too.<br /><br />BTW: There is a separate debate on society journals versus open access journals. Open access journals (along with the arxiv) win on availability but longevity may be an issue for those that do not have a "pay-to-publish" model. From the point of view of serving their members the ideal would be a society-published open-access journal. I guess there is the problem that someone has to pay the headquarters staff.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31862024507497541852009-07-27T19:15:31.154-05:002009-07-27T19:15:31.154-05:00I can't add much after 100 comments, but:
rep...I can't add much after 100 comments, but:<br /><br />reply to Paul Beame: what is wrong with (T)CS adopting the practice of mathematics, which attacks 1 - 5 as follows?<br /><br />1) arXiv (why are there so few CS papers there?)<br />2) invited addresses, workshops, special sessions, prizes, Mathematical Reviews, blogs (in particular, why is Computing Reviews so little used in CS?)<br />3) journals<br />4) open source, followed by society journals (there are problems with free-to-read-but-not-to-write journals as is becoming common, but progress is possible)<br />5) electronic journals (arXiv overlays?)<br /><br />Reply to aravind: a concrete suggestion for improving papers - editors should require that each paper explicitly contain a literature review and a section called "our contribution" that explains how the present paper improves on the past, and why we should care about such an advance. <br /><br />Requiring people to referee in proportion to their publishing would certainly reduce the number of papers, especially if their referee reports could be rejected if challenged as inadequate by the authors.Mark Wilsonhttps://www.blogger.com/profile/16382201587698895101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49088394579542043962009-07-27T18:41:06.679-05:002009-07-27T18:41:06.679-05:00^^^^
I like Yoav Freund's idea of a forum for...^^^^<br /><br />I like Yoav Freund's idea of a forum for TCS very much. Blogs are directed by a single (or, in this case, a couple of) individuals. It would be an interesting experiment to have multiple threads controlled by a community. This would be especially valuable for people who are not in major research institutions, and it would give a source of feedback, other than conference PC reviews, about the significance of results.Unknownhttps://www.blogger.com/profile/16095579069590680426noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82682891445040789732009-07-27T17:50:25.050-05:002009-07-27T17:50:25.050-05:00I agree with Lance that there is a big problem of ...I agree with Lance that there is a big problem of the significance of conferences pushing people in CS towards rushed publications and conference proceedings that represent the "smallest publishable unit".<br /><br />However, I don't think that paper journals are the solution. The editorial boards of journals tend to be conservative and reject work that is new and different.<br /><br />I believe that the fundamental problem is that good and significant work takes time to mature. Rob Schapire and I are finally finishing a book about boosting which was 10 years in the making, and I am still not quite satisfied with the way the more recent work on boosting is described in the book.<br /><br />This long maturation time can result in problems of assigning credit where credit is due. There has to be some way for people to publish papers that are at a relatively initial stage and secure their credit. The solution that I use is to publish papers on Arxiv. This is a way of making papers available to peers while maintaining a record of the contributions of yourself and your students.<br /><br />Then comes the issue of publicity and quality assurance. It is not enough to make papers available, there are just too many papers. There have to be mechanisms for helping people find good papers and for helping authors find receptive audiences. This need is supposed to be filled by conference program committees and by the editorial boards of journals. However it is clear that these mechanisms are not sufficient and new mechanisms are needed.<br /><br />I have started a web site whose goal is to provide such a mechanism for machine learning and related areas. The name of the web site is <br />themachinelearningforum.org.<br /><br />The basic idea is that anybody can submit a link to a paper and that people with a proven track record can write reviews of papers (but not of their own papers). The reviewer of a paper is not anonymous, so people get some credit for writing a good review.<br /><br />This site has been up for about a month now, and we are still working on it. Initial response has been very good, but it remains to be seen if it will take on the role I hope it will have. If you are interested in Machine Learning, please register to the site and contribute.<br /><br />It would be a relatively easy thing to start a similar site for theoretical computer science. I would be happy to help.Yoav Freundhttps://www.blogger.com/profile/06452936023657718965noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81350783144013454932009-07-27T14:42:45.911-05:002009-07-27T14:42:45.911-05:00"As an outsider I have always thought that ST..."As an outsider I have always thought that STOC and FOCS were THE top two CS conferences of equal standing."<br /><br />They are, of course. Or better to say: they *were* such. New trends enrolled in the meanwhile ...<br /><br />"The bad is only working for a paper and not for the scientific enlightenment."<br /><br />I agree completely. Not only I: see <a href="http://agtb.wordpress.com/2009/05/14/readerless-publications/" rel="nofollow">Noam's</a> very nice remarks on this.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39056152653581532662009-07-27T14:23:59.287-05:002009-07-27T14:23:59.287-05:00frankly, I am amazed it did not get into STOC or i...<i>frankly, I am amazed it did not get into STOC or its weaker cousin FOCS.<br /></i><br /><br />As an outsider I have always thought that STOC and FOCS were THE top two CS conferences of equal standing.<br />Is it true that there is indeed a diferentiation between even these two in terms of prestige ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38751907203026582412009-07-27T13:53:42.331-05:002009-07-27T13:53:42.331-05:00"Stacy, the bad is not rediscoveries. It is j..."Stacy, the bad is not rediscoveries. It is just used as an example." <br /><br />Yes, this clear. "Big" damages are best seen on examples. And I agree with what you said later.<br /><br />But I cannot completely agree with <br />"The bad is not making an attempt to do a literature search." Not trying to search is bad, no doubts. But we do this! We try to do this! However, we live with "google" or "google scholar", etc. And they just show us a "pot", not what the "soup" is there. So, we should trust much more to our "older" colleagues. They know much more. But how can this be realized within a HARD competition? This is the problem.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.com