tag:blogger.com,1999:blog-3722233.post111827256269899485..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Growth Causes ShrinkingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger31125tag:blogger.com,1999:blog-3722233.post-1119039819426869222005-06-17T15:23:00.000-05:002005-06-17T15:23:00.000-05:00postscript:Also, please do not stay in a funk that...postscript:<BR/><BR/>Also, please do not stay in a funk that the rest of TCS does not appreciate your area. Tell the rest of us about it! <BR/><BR/>Everybody is busy and loses track of what is going on outside their narrow specialty. One of the joys of my participation in TCS advocacy this spring is that I have learnt a lot about the diverse impacts of TCS. I am curious to learn more. BTW, I was the chief writer of the document on theorymatters.org (though I was a scribe for an informal group of 6-8 people). <BR/><BR/>pps: Why TCS and not "theory"? <BR/>Dick Lipton suggested this change of name. He pointed out that too many people have a negative connotation with "theory." (Think "theory of evolution.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119039404226261742005-06-17T15:16:00.000-05:002005-06-17T15:16:00.000-05:00As one of the people active in theory advocacy, I ...As one of the people active in <BR/>theory advocacy, I have a few comments. Pls especially see (iv).<BR/><BR/>(i) My sense was that the TCS community (interpreted broadly) is <BR/>suffering uniformly from funding problems. Furthermore, it is more united than any time I personally recall. Speaking for myself, I would be interested in having all kinds of theory (including everything mentioned here) represented at STOC/FOCS or some kind of umbrella TCS conference.<BR/><BR/>(ii) Everybody should get involved. The more diverse viewpoints are represented, the stronger our case. <BR/>Everybody should become an ambassador for TCS. Don't assume that the Karps or the Wigdersons will take care of this (though both of them are also involved).<BR/><BR/>(iii) I repeat Boaz's point: theorymatters.org is a wiki. Please contribute to it. No single person has the time to maintain it; it belongs to all of us. <BR/><BR/>(iv) Please do something that will actually have an effect. (Writing comments on a blog like this that is read only by insiders does not count.) Write a 1-2 page description of a nice TCS contribution/challenge and send it to CACM. (Or just put it on theorymatters.org, so it can be used in the ongoing TCS advocacy.) Figure out whom to lobby in Congress or the National Science Board or the CISE advisory board (your university administrations can help you with the congress part) and do it and tell the rest of us about it. Compose a form letter to your senator/congressman and distribute it to the rest of us so we can all send it to our local senators/congressmen. <BR/><BR/>(v) Random anecdote: on the mailing list associated with theorymatters,<BR/>I posted an email asking for suggestions about important challenges for TCS ---preferably phrased in language that congressmen and CISE board members can understand. Number of responses: two. (And this was in late May, after the end of spring term.)<BR/><BR/>SanjeevAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118970142563219532005-06-16T20:02:00.000-05:002005-06-16T20:02:00.000-05:00Nobody would ever say "ugh! it has geometry in it,...Nobody would ever say "ugh! it has geometry in it, should go to SoCG" -- geometry is beautiful, one cannot be worse than indifferent to it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118855576677463822005-06-15T12:12:00.000-05:002005-06-15T12:12:00.000-05:00Some opinions:1. There should *not* be any "inside...Some opinions:<BR/><BR/>1. There should *not* be any "inside areas" for STOC/FOCS. A paper should always be accepted only on basis of quality and not because it "belongs" to STOC/FOCS. Maybe there was such a need in the past for areas that seemed very important but simply did not have any other home. I don't think this should be the case today.<BR/><BR/>No one working in area should expect to have the "luxory" of only needing to go to STOC/FOCS to see all the interesting results.<BR/><BR/><BR/>2. Sometimes people have a more insular view of STOC/FOCS than reality. I wonder if commenters working in logic, CG, etc actually tried to send a few of their best papers to STOC/FOCS and were rejected. (One wrong rejection doesn't count - committees make mistakes all the time)<BR/><BR/>3. STOC/FOCS program chairs should be vigilant to guard against being insular and also the preception of being insular (since if you're preceived as insular you won't get the good papers, and it would do no good that you would have accepted them).<BR/><BR/>4. Don't give "theorymatters.org" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.<BR/><BR/><BR/>--boazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118653959236326642005-06-13T04:12:00.000-05:002005-06-13T04:12:00.000-05:00Both results are about randomness and its role in ...Both results are about randomness and its role in computation. If you're describing their importance to a colleague, that is where the story should begin. Oh, and another theoretical achievement of the past 15 years--derandomization is fundamentally tied to some of our community's most compelling unsolved questions (i.e. P vs. NP, circuit lower bounds). This is an astounding and beautiful story.<BR/><BR/>The problem with describing SL = L as a way to "solve mazes" with bounded memory is that for mazes, the "right hand rule" seems to work just fine.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118584840015556212005-06-12T09:00:00.000-05:002005-06-12T09:00:00.000-05:00Just to defend myself...1) I agree with Luca's st...Just to defend myself...<BR/><BR/>1) I agree with Luca's statement that there is no contradiction -- one can be proud of the work done in the last few years while wishing STOC/FOCS was even broader. What struck me about Luca's list was how complexity-oriented it was; surely it would be nice, from my point of view, to see some more algorithmic items on the list of STOC/FOCS success stories. And they would add to the case of why theory is important to the "outside world" -- though, as Luca says, we should certainly try to trumpet these successes as well.<BR/><BR/>2) Apparently the anonymous author had a different experience with his/her colleagues after the Primes in P result than I did. Non-theorists generally fell into 2 camps. Almost everyone fell into group 1 -- they realized it was a big problem for theory and were glad we had solved it, but didn't have any idea how the result was done or why it was important. So they recognized it as a challenge, in the same manner as Fermat's Last Theorem was a challenge, and they understood the result about as much as I understand the proof of Fermat's Last Theorem. <BR/><BR/>A smaller number fell into group 2. These were either mathematicians, or mathematically trained people, who wondered why we all thought the result was such a big deal. There are faster randomized primality tests out there, so the actual impact on cryptography is not yet clear, but the feeling was it might well be nothing. (So, yes, I don't see how to explain the implications of this result in cryptography to non-theorists -- I'm not a cryptographer, so perhaps someone should explain them to me!) They weren't surprised by the result, and apparently they didn't think the result had the mathematical magnitude of something like a Fermat's last theorem. <BR/><BR/>I think explaining SL = L as a result on mazes is an interesting idea... my concern would be that such a description would lose the reasons why the result is important, from a complexity point of view, and make it seem like a "puzzle problem". But perhaps one could get across the significance to non-theorists that way.Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118553928596020742005-06-12T00:25:00.000-05:002005-06-12T00:25:00.000-05:00While Lance's version of the break-off of the Stru...While Lance's version of the break-off of the Structures conference (now Complexity) and LICS is correct I don't think that it is an accurate reflection of what happened in most other areas.<BR/><BR/>In the late 1980's, the fixed single track size of STOC/FOCS and the increase in size of the community led to a situation in which only a small portion of the good work in an area would actually be accepted at STOC/FOCS because the number of papers that would fit was limited. Many areas formed their own conferences where a larger fraction of the work in their specialty could be presented. At about the same time, NSF travel budgets were cut significantly and this led to some reduction in participation in FOCS/STOC as people found more of their specialty represented in their own conferences (and to some extent could only afford to go to conferences in which they had papers.)<BR/><BR/>The spin-off conferences of the 1980's have often worked out arrangements that have convenient timing with respect to STOC/FOCS submission dates. FCRC has brought many of these spin-off conferences together and Complexity and WAW, for example, co-locate with STOC/FOCS frequently even outside of FCRC.<BR/> <BR/>Computational Geometry is somewhat unusual in choosing to separate itself and very quickly directly conflict with STOC. I don't believe in any way that this is because Geometry was not well received at STOC/FOCS. Good computational geometry papers still show up at FOCS/SODA but the separation is a loss for both the Computational Geometry community and STOC/FOCS. Indeed, some of the hottest topics in recent STOC/FOCS has been in the use of the geometry of metric spaces. Surely there is no reason that computational geometry needs to be as separated as it is and there would be benefit of greater interaction.<BR/><BR/>FOCS/STOC are the premier Volume A theory conferences. They still represent that portion of theory quite broadly. I think it would be unfair to attempt to make any sharper distinction.<BR/><BR/>The situation with LICS and logic is more complicated. Unlike SOGC and most of the other 1980's spin-off conferences, LICS covers Volume B topics. Logic is certainly not excluded from STOC/FOCS - some topics have both Volume A and Volume B aspects (proof complexity, complexity of logical algorithms etc.) but the fit for STOC/FOCS is much less good for some topics. Even in the early 1980's the co-existence of Theory A and Theory B topics at FOCS/STOC was an uneasy one and it is hard to see the trend of separation between the two reversed. (The Federated Logic Conference FLoC in many ways may be Theory B's natural counterpart to <BR/>STOC/FOCS.) <BR/><BR/>The Bottom Line:<BR/><BR/>STOC/FOCS are extremely vital and active. This also means that competition to get papers into these conferences has probably never been tougher. Nonetheless Theory A reserarchers will all better off if we are not isolated in our narrow and comfortable communities but, despite the tougher odds, contribute to the broader conversation at STOC/FOCS. A huge amount of the progress in theory has been because of the tremendous cross-fertilization within our field.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118536562488409362005-06-11T19:36:00.000-05:002005-06-11T19:36:00.000-05:00I am shocked that Michael cannotexplain the signif...I am shocked that Michael cannot<BR/>explain the significance of<BR/>Primes result to non-theorists<BR/>in CS. Aren't the implications to<BR/>cryptography clear? Even the SL=L result can be explained as an <BR/>algorithmic result for exploring<BR/>mazes. I agree with Luca that we<BR/>we need to convey our excitement<BR/>to outsiders. If we ourselves do<BR/>not believe in the significance<BR/>of these results the the CS field<BR/>as a whole, we have an uphill battle ahead of us.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118482993881200862005-06-11T04:43:00.000-05:002005-06-11T04:43:00.000-05:00There isn't a contradiction here: one can be proud...There isn't a contradiction here: one can be proud of all the successes of the last few months and years, and of the fact that one sees more connections between "stoc/focs theory" and mathematics, statistics, physics, economics and biology, and at the same time wish that stoc/focs were even broader.<BR/><BR/>But I disagree on a point with Michael. One can communicate the excitement of what is going on now in theory to the average computer scientist. In fact one <B>must</B> do so as part of any advocacy effort. Saying "we haven't accomplished much lately, but if you give us more money we'll start doing something else" is not a winning argument either. <BR/><BR/>Also, the fact that the latest set of results makes theory more respectable in mathematics and science circles is a good thing, not a liability. Part of the bigger computer science funding crisis comes from the fact that computer science is seen from outside as a purely engineering discipline: a provider of infrastructures. So now that we have the internets, email, and windows, there are no more fundamental computer science problems to solve and we just need to produce more computers. The case that computer science is also truly a science and that it works on fundamental problems is an important case to make for all computer science, and theory should be at the core of this argument.<BR/><BR/>Arora and Chazelle wrote an op-ed that makes some of these points (I am doing a very poor job at summarizing them, while their article is very good) and it is to appear in CACM. There is also a copy on theorymatters.org under FundingCrisisLinks.<BR/><BR/>LucaLucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118428974873394432005-06-10T13:42:00.000-05:002005-06-10T13:42:00.000-05:00In response to some of the comments above:1) Havi...In response to some of the comments above:<BR/><BR/>1) Having been to INFORMS, I think we could never get a theory conference that big-- and that's a good thing. Having attended one, I can say I found 50 parallel sessions is just too much; you really do have problems just reading the program, and finding what room to go to!<BR/><BR/>3-6 parallel sessions, in rooms close enough that you can get from one to other if you want, works quite well. FTRC -- combining 4-5 conferences, with a goal of say 500+ attendees -- would be a great idea; not too big that you can't meet new people, but big enough to be the first major theory get-together of its type that I can think of. (FCRC doesn't count, for obvious reasons.)<BR/><BR/>2) I wouldn't want to deny that theory as a whole is doing well -- I think it is. But Luca's post seems just off to me (apologies, Luca!), especially considering recent postings we've had regarding the dire funding situation in theory, and actually reinforces my "concerns" that STOC/FOCS is too narrow. Pretty much every example he cites (with the exception of Jon Kleinberg's work) is something I would have trouble explaining the importance of to non-theorists. Even the smoothed analysis results and the primes in P results, which I could easily explain, seem to be results that would apply more to mathematicians rather than computer scientists, and I don't think that's going to impress on the rest of the world the importance of theory, even if the results are very nice. <BR/><BR/>In short, I think the attitude "STOC/FOCS is healthy, just look at these results" is a point of view that risks growing the mindset among our colleagues theory is unimportant to the rest of computer science.Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118416795696609212005-06-10T10:19:00.000-05:002005-06-10T10:19:00.000-05:00"I think is a status quo kind of thing. A few bene..."I think is a status quo kind of thing. A few benefit from this state of affairs"<BR/><BR/>This is the mindset that will knock down attendence to theory conferences.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118413275047303272005-06-10T09:21:00.000-05:002005-06-10T09:21:00.000-05:00See the example of SoCG: only 41 papers accepted w...<I>See the example of SoCG: only 41 papers accepted when, according to Ernie, 90 were acceptable! </I><BR/><BR/>This just boggles the mind.<BR/><BR/><I>Why not to open concurrent sessions, and make this a better event?</I><BR/><BR/>I think is a status quo kind of thing. A few benefit from this state of affairs, and heavily defend it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118378275184745702005-06-09T23:37:00.000-05:002005-06-09T23:37:00.000-05:00Despite being declining, insular and narrow, STOC/...Despite being declining, insular and narrow, STOC/FOCS is doing quite well.<BR/><BR/>In the past few <B>months</B> we have heard of Reingold's L=SL, Trifonov's completely different and almost as good result, Dinur's new proof of the PCP theorem, the Khot-Vishnoi refutation of a ten years old conjecture of embeddability of L_2^2 into L_1, Morris's confirmation of a twenty years old conjecture about the Thorp shuffle, the breakthroughs in the constructions of bipartite Ramsey graphs (it's hard to tell how old were those conjectures) and the proof of the "majority is stablest" conjecture.<BR/><BR/>(Plus other things that I am surely forgetting)<BR/><BR/>Going back a few years, we see that the Annals of Mathematics has four recent papers (appeared or in press) from STOC/FOCS: primes in P, the zig-zag expanders, the Dinur-Safra hardness of vertex cover, and the paper on metric Ramsey-type theorems.<BR/><BR/>Jon Kleinberg published in the last few years one paper in Science and one in Nature related to STOC/FOCS papers (possibly more, these two are the ones that I know of).<BR/><BR/>Smoothed analysis was cited by CISE (the NSF division for all of computer science) as one of three significant discoveries in all of computer science in its 2003 budget request to congress.<BR/><BR/>This is not to deny that distributed computing, computational geometry, machine learning and other areas are not sending their best papers (or even any papers) to STOC/FOCS, that everybody loses because of that, and that we need to do something about it. Having a more diverse program committee and colocating conferences are both good ideas.<BR/><BR/>I just think that it is ridiculous to claim that STOC/FOCS is declining even while we are coming from a few years of spectacular success, or to charge that it is insular, even as the connections with mathematics, statistics, biology, physics and economics are expanding. It sounds like the joke of the Englishman who sees fog over the Channel and says "the continent is isolated."<BR/><BR/><BR/>Luca<BR/><BR/>P.S. And let's not forget about the impossibility of obfuscators, the ARV sparsest cut algorithm and its implication for other problems and for metric embeddings questions, the construction of cryptographic protocols that are impossible in the black-box model, and several other breakthroughs that I cannot recall off the top of my head.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118377725251767142005-06-09T23:28:00.000-05:002005-06-09T23:28:00.000-05:00I think this is a consequence of the model of conf...I think this is a consequence of the model of conferences that CS has adopted (which is not the best, in my opinion). The idea that only a small fraction of the submitted papers should be accepted is clearly excluding for large parts of the community. See the example of SoCG: only 41 papers accepted when, according to Ernie, 90 were acceptable! Why not to open concurrent sessions, and make this a better event?<BR/><BR/>FOCS/STOC also have the potential of being better, if only the community is able to be more inclusive and care less for "acceptance ratios", which is a notion that says absolutelly nothing. Having more people (working in the area) participating in a conference is more important than having strong proceedings: publication is a matter for journals.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118372781488583882005-06-09T22:06:00.000-05:002005-06-09T22:06:00.000-05:00I don't agree with the decline in quality from the...I don't agree with the decline in quality from the early 80s until now, either. Also I don't think people are suggesting that a certain percentage of papers is pre-allocated to any area. What it is suggested is that PCs make the decision based solely on quality just as you suggested instead of on attitudes such as "ugh! it has logic in it, should go to LICS" or "ugh! it has geometry in it, should go to SoCG".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118372080670577322005-06-09T21:54:00.000-05:002005-06-09T21:54:00.000-05:00INFORMS doesn't have as much prestige as a FOCS pa...<I>INFORMS doesn't have as much prestige as a FOCS paper, but it is a huge meeting (~50 parallel sessions)</I><BR/><BR/>50 parallel sessions! How are you even supposed to read the conference program?!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118364321138810142005-06-09T19:45:00.000-05:002005-06-09T19:45:00.000-05:00Another interesting example is INFORMS annual meet...Another interesting example is INFORMS annual meeting. INFORMS doesn't have a published proceeding or refereeing process, so presenting a paper in INFORMS doesn't have as much prestige as a FOCS paper, but it is a huge meeting (~50 parallel sessions) where everyone in the operations research & management sciences community gathers. It's very well attended, and it also provides a good place for potential employers to interview graduating students.<BR/><BR/>Given the difficulty of making acceptance/rejection decisions when the conference is too broad, I think if we want to have occasional meetings for the entire theory community, the solution is to either go with something like FTRC, or something like INFORMS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118352565761183882005-06-09T16:29:00.000-05:002005-06-09T16:29:00.000-05:00I don't agree with you that there has been a decli...I don't agree with you that there has been a decline in the quality of FOCS/STOC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118352339056038312005-06-09T16:25:00.000-05:002005-06-09T16:25:00.000-05:00Although it might seem to be have little significa...Although it might seem to be have little significance to the subject matter of the discussion, I feel that a substantial part of the problem is some kind of "race" in the community. Most of the people want a large number of publications at the cost of quality. I was going through the FOCS proceedings from early 80s and felt that there has been a substantial decline in the standards. <BR/><BR/>This is one of the reasons why "outsiders" (courtsey Moshe Vardi) feel that they do not have a substantial share in STOC and FOCS. The problem is that there are a large number of papers in Complexity/Algorithm which are rougly of the same quality and hence it becomes difficult to distinguish. I strongly advocate that there be some element of self censorship in the theory community. This is something which we should learn from our friends in Math department. Even a mathematician of first order does not have more than 10 publications in Annals of Maths. This way we will have STOC and FOCS representing the ture status of the theory of computing.<BR/><BR/>Most importantly, I feel that the "communist" attitude of having a balance between subfields is going to take us nowhere. The sole criterion for a paper being accepted should be its quality.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118350648898590362005-06-09T15:57:00.000-05:002005-06-09T15:57:00.000-05:00Smaller conferences do have an advantage. I've nev...Smaller conferences do have an advantage. I've never been to INFOCOMM, but from what I've heard I much prefer a model like Crypto where there are "only" 300-400 attendees and so it is feasible to actually meet new people. <BR/><BR/>By the way, I don't think STOC/FOCS is insular so much because of the "insiders" (whoever they are) as because of the program committee members. Clearly, if you want CompGeom papers to get in, you need to have at least one CompGeometer on the committee. Note to the next program chair of STOC/FOCS: if you want a more diverse program, pick a more diverse program committee.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118336925182045042005-06-09T12:08:00.000-05:002005-06-09T12:08:00.000-05:00Should we float the FTRC idea with ACM/SIGACT? Hal...Should we float the FTRC idea with ACM/SIGACT? <BR/><BR/>Hal Gabow are you out there?<BR/><BR/>Say, how about FTRC 2008, with the traditional Spring theory conferences, i.e. CC, SoCG, STOC, SPAA and PODC (if they agree)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118276734368227072005-06-08T19:25:00.000-05:002005-06-08T19:25:00.000-05:00This comment has been removed by a blog administrator.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118332331087516422005-06-09T10:52:00.000-05:002005-06-09T10:52:00.000-05:00There is a lot of issues raised by this post... I'...There is a lot of issues raised by this post... I'll focus on echoing supporting the idea that theory needs <B>larger</B> conferences (or several co-located conference, an FTRC) bringing the community together, rather than so many small conferences and workshops. (FOCS/STOC/SODA, while on the large side, are really the minimum size we should be aiming for.) Reasons include:<BR/><BR/>1) Limited travel budgets: with grants ever shrinking, there are fewer conferences I can reasonably go too. It's more cost-effective to have one big theory conference to attend and send multiple papers to. <BR/><BR/>2) Publicity: It would give theory somthing to point to, to show that we are a large and productive community. It might also (if done right) get more "non-theorists" to attend and see the wonderful things we are up to. (Lots of theory people go to networking conferences -- let's get more networking people to theory conferences!) <BR/><BR/>3) Unity: It could counteract the theory trend of increased specialization and division into smaller subgroups.<BR/><BR/>One model I like is the Allerton model, a conference covering perhaps somewhat disparate areas including networking, coding, information theory, etc. It's run by people at UIUC every year -- giving a wonderful consistency in organization. It's "small" -- these days, about 300 attendees. It generally has 6 parallel sessions in a huge variety of areas; there's always plenty of stuff I don't care about, but almost always a talk going on I want to see, and plenty of people to talk to. <BR/><BR/>Another example is INFOCOM. It's huge. It's ugly. (A common complaint is that there are a lot of less-good papers at INFOCOM, although I think that's been getting better.) But it's the place to go to see what's going on in networking.<BR/><BR/>I'd love a theory conference more like one of these. Sure, having 6 parallel sessions isn't always so great, but it gets people all in the same place, and there's something to be said for that.Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118331603412153692005-06-09T10:40:00.000-05:002005-06-09T10:40:00.000-05:00As a side remark since most of this discussion has...As a side remark since most of this discussion has been about STOC/FOCS, I think the original posting was a bit unfair about SODA, and expect the remark about the PC meeting is apocryphal. This conference always has computational geometers on its program committee and this year had an invited talk and two sessions devoted to CG.<BR/>In general, we've made an attempt to be inclusive (within the area of algorithms for discrete problems) although we're certainly not perfect.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1118327144655420712005-06-09T09:25:00.000-05:002005-06-09T09:25:00.000-05:00I agree that STOC/FOCS has become insular and ther...I agree that STOC/FOCS has become insular and there is a tendency for<BR/>the insiders to think that they are <BR/>the "true" representatives of theory and somehow that their work is not as specialized as those of other <BR/>sub-areas that have branched out.<BR/>This is unwise in the long run. <BR/>(I am an insider btw).<BR/><BR/>I believe that most of the problems <BR/>are caused by the firmly entrenched <BR/>belief in CS that conferences that <BR/>confer prestige on the selected <BR/>papers is the "right way". There <BR/>is very little incentive<BR/>to change this practice because<BR/>of tenure pressures etc. I don't<BR/>believe that this is a good model<BR/>for theoretical areas that would<BR/>benefit from quick exchange of <BR/>ideas. I have often felt that it <BR/>would be great to attend SoCG or <BR/>COLT or CRYPTO but it is difficult <BR/>to go to many conferences.<BR/><BR/>In the short term, I think a good<BR/>compromise might be to co-locate<BR/>several theory conferences once<BR/>in a while to bring the people <BR/>together.Anonymousnoreply@blogger.com