tag:blogger.com,1999:blog-3722233.post7174737273233746291..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: STOC 2011 accepte papers posted.You heard it here...12th!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-65622024590518074532011-02-11T20:09:41.026-06:002011-02-11T20:09:41.026-06:00A great (unrelated) article by "Time" fr...A great (unrelated) article by "Time" from 1982 on cryptography.<br /><br />http://www.time.com/time/magazine/article/0,9171,953625-1,00.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38530713987915808952011-02-11T00:18:13.279-06:002011-02-11T00:18:13.279-06:00There is a related statement toJust because a pape...There is a related statement to<i>Just because a paper "has an algorithm" in it does not mean it's an algorithms paper.</i><br /><br />Also, just because a paper "is not an algorithms paper" does not mean it's a complexity paper. Too often I see some sort of sniping in blog comments seeing these as two competing poles. To me, a noticeable feature of our field (and very evident in the STOC program) has been the growth of topics and papers that don't neatly fit in the spectrum between these two poles. <br /><br />Micha Sharir gave a plenary talk at SODA a few years back making the point that for computational geometry, at least, among the most important directions was the solution of underlying combinatorial and geometric questions, independent of any specific algorithm. This kind of thing has become increasingly true in other aspects of TCS.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10411328353670732702011-02-10T22:36:25.280-06:002011-02-10T22:36:25.280-06:00Nick --
Cool! Thanks for the info!
MikeNick --<br /><br />Cool! Thanks for the info! <br /><br />MikeMichael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63482862144975700842011-02-10T19:27:28.201-06:002011-02-10T19:27:28.201-06:00Michael,
It is perhaps not apparent from the titl...Michael,<br /><br />It is perhaps not apparent from the title & abstract which algorithms are possibly practical.<br /><br />Our paper "A General Framework for Graph Sparsification" gives a variant on the Benczur-Karger algorithm that is quite a bit simpler to implement. I was tempted to implement it myself, just for fun, but decided to wait until I have an undergrad looking for a term project.<br /><br />Another good paper to try to implement would be "High-rate codes with sublinear-time decoding". For this one, even the abstract hints that it might be practical. There could be many interesting applications if the algorithm were indeed practical.<br /><br />I think you've previously commented on "The Power of Simple Tabulation Hashing", but for the sake of others who haven't seen it, I'll point out that they even did an experimental evaluation.Nick Harveyhttp://www.math.uwaterloo.ca/~harvey/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50300554130684723852011-02-10T03:04:53.437-06:002011-02-10T03:04:53.437-06:00> Well, seeing as you rushed to
> post a lin...> Well, seeing as you rushed to<br />> post a link to the STOC accepted<br />> papers even before the public<br />> list is available, but never<br />> commented on the list of papers<br />> accepted to SODA, this may be<br />> indicative of the "general<br />> trend".<br /><br />This is supposed to be a complexity blog, so they have no obligations to blog about conferences with a different focus. But Bill/Lance could have at least posted a list of lower bound papers in SODA (they can still do it).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54490570781324310652011-02-09T22:04:13.322-06:002011-02-09T22:04:13.322-06:00Warren:
I certainly didn't mean to suggest th...Warren:<br /><br />I certainly didn't mean to suggest that I was defining algorithms -- just the opposite, I said that the term was overloaded with meanings.<br /><br />But if your interpretation of what I mean was that I thought some people lamented the apparent lack of possibly practical algorithms in FOCS/STOC, that sounds right!Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89091704442429590552011-02-09T20:15:11.306-06:002011-02-09T20:15:11.306-06:00Michael M. defines an "algorithm" to be ...Michael M. defines an "algorithm" to be a positive result that might expected to be implemented. Surely we can find a better name for that than "algorithm". Maybe "practical algorithm" or "possibly practical algorithm".<br /><br />Warren S.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61372889895989008702011-02-09T18:01:19.175-06:002011-02-09T18:01:19.175-06:00Though I wasn't part of this, I'll bet tha...Though I wasn't part of this, I'll bet that 84 was actually a real limit. <br /><br />There are very signficant constraints on the # of papers in ANY 3-day 2-track conference assuming a minimum of 20 min talks with 5 min to move between talks in the middle of sessions. This can comfrotably be as many as 96 papers, 32 per day organized in four 95 min parallel sessions each having 4 papers. With a 30 min bathroom/coffee break you get 3:40 min total per half-day. This would be 8:50-12:30 and 2:00-5:40 for example. Any award/plenary talk of the same length subtracts 1 from the number of papers and also adds extra time to move between session formats. <br /><br />By making people uncomfortable one can add one extra pair of talks each day to get to 102 total (minus the number of award talks).<br /><br />At FCRC there is an hour in the late morning slated for FCRC-wide plenary talks. Each such talk would kill slightly less time than 6 talks for a total of almost 18 talks over 3 days which gets you 84 talks. The only way that they'll get award/plenary talks in is by slight juggling because the cost of each is "slightly" less than 6 talks.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1490070416620013652011-02-09T17:30:23.082-06:002011-02-09T17:30:23.082-06:00"Are there too many different subfields of CS..."Are there too many different subfields of CS that don't care about each other to really have a conference like that?"<br /><br />Is the Grace Hopper Conference about caring about each other as people (specifically as women in CS) rather than caring about actual disciplines?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32927919659412283662011-02-09T16:10:56.586-06:002011-02-09T16:10:56.586-06:00Well, seeing as you rushed to post a link to the S...Well, seeing as you rushed to post a link to the STOC accepted papers even before the public list is available, but never commented on the list of papers accepted to SODA, this may be indicative of the "general trend".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12237533192676158952011-02-09T13:46:45.824-06:002011-02-09T13:46:45.824-06:00BTW (perhaps I am showing my age) but 'jaw-som...BTW (perhaps I am showing my age) but 'jaw-some' comes from the horrible nineties cartoon 'Street Sharks'. They were sharks with legs. I was in middle school back then. It was their catch phrase.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31457010317026817822011-02-09T12:56:53.944-06:002011-02-09T12:56:53.944-06:00There are also several papers on graphs/networks a...There are also several papers on graphs/networks algorithms (I have no idea whether they will be used in the nearish future).Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84251044349160523532011-02-09T12:56:14.444-06:002011-02-09T12:56:14.444-06:00MM- no insult intended--- I meant a conference tha...MM- no insult intended--- I meant a conference that WELCOMES all branches of CS.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90856879006777306482011-02-09T12:49:20.207-06:002011-02-09T12:49:20.207-06:00Anon #3 : Just because a paper "has an algor...Anon #3 : Just because a paper "has an algorithm" in it does not mean it's an algorithms paper. When I have an algorithm in a coding theory paper, I still call it a coding theory paper. (When a biology paper has a differential equation in it, that doesn't mean we should call it a math paper.) <br /><br />Having had this "discussion" before, I think an issue is that "algorithm" has just now become overloaded. I think when people say there aren't many "algorithms" paper, they mean there are comparatively fewer papers about algorithms that people actually use or may want to use in the near-ish future to solve an actual problem (as opposed to making a mathematical point). Of course, other people saying that may mean something different, and perhaps they'll chime in. <br /><br />----<br /><br />Bill --<br /><br />I'm assuming you didn't mean to be denigrating with that Kumbaya comment, but it didn't sound so nice to me. I just got back from the still-going-on ITA workshop (http://ita.ucsd.edu/workshop.php) -- a very broad and big get together of information theorists (and others -- they seem to be inviting more computer scientists). They also do the big get together thing at the annual Int'l Symposium on Information Theory conference. These things tend to be 5 or so days, with various business meetings, awards ceremonies, special lectures for grad students (career training and such) entertainment, etc. scheduled to coincide. ISIT, last I checked, gets 700-800 attendees regularly. <br /><br />There are pros and cons to both conference approaches, certainly. I wouldn't try to deny that larger, more open conferences have the tradeoff that average paper quality is lower, and the hassle of figuring out which parallel session to go to can be frustrating. But I'm consistently surprised at the reluctance of the TCS community to seriously consider this as an option.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35611659468048216892011-02-09T11:20:44.525-06:002011-02-09T11:20:44.525-06:00What counts as algorithms? There are plenty of pap...What counts as algorithms? There are plenty of papers that are not in "complexity theory" -- game theory, learning theory, privacy, cryptography, metric embeddings. The main results in many of these papers are algorithmic. Do they not count?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49210641695504621342011-02-09T10:14:24.228-06:002011-02-09T10:14:24.228-06:00This is amazing breaking news to share. Thank you...This is amazing breaking news to share. Thank you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57536082227728958222011-02-09T10:09:33.881-06:002011-02-09T10:09:33.881-06:00My impression is that good papers in complexity ar...My impression is that good papers in complexity are being accepted and no good (only great--unless they have some AGT connection) papers in algorithms are accepted. So yes, that is a problem.Anonymousnoreply@blogger.com