tag:blogger.com,1999:blog-786333285568106173.post1455544202856582962..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: STOC'08 updateMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-786333285568106173.post-13189234284490836622008-05-21T12:26:00.000-04:002008-05-21T12:26:00.000-04:00The distinction between approximation and non-appr...The distinction between approximation and non-approximation algorithms is not quite mine. Talk to people at SODA. There is actually some tension between the fields. People in approximation tend to think improvements to polynomials are not theoretically fundamental and should only be done for the sake of practice. People in non-approximation complain that approximation people form a clique which pushes too many papers in; there are too many problem variants in the field (see the travelling dog and pony); and that the field has ultimately had very little impact outside theory (the common argument that people in practice like to approximate their problems to within 2%, not within a log factor).<BR/><BR/>Of course there are relations between the fields. But there are also important relations eg between CS and functional analysis, and nobody thinks the fields are identical.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-68255377175640052322008-05-21T12:18:00.000-04:002008-05-21T12:18:00.000-04:00Thanks for the link; it was an entertaining read. ...Thanks for the link; it was an entertaining read. But it seems my intention was misunderstood. I wasn't trying to "disagree" with this guy.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-10966161519736391032008-05-21T01:48:00.000-04:002008-05-21T01:48:00.000-04:00Call me Ishmael.Call me Ishmael.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-1694643993286450832008-05-20T19:10:00.000-04:002008-05-20T19:10:00.000-04:00Mihai,see DH0 in http://www.paulgraham.com/disagre...Mihai,<BR/>see DH0 in http://www.paulgraham.com/disagree.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-518173423585865272008-05-20T17:09:00.000-04:002008-05-20T17:09:00.000-04:00Anon, arguments from frustrated, insignificant mem...Anon, arguments from frustrated, insignificant members of the community have as much weight as their author. Though you fail to reveal your identity, your tone has just about enough information...Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-82534561649467709862008-05-20T17:02:00.000-04:002008-05-20T17:02:00.000-04:00So lets sum up: The argument that there are no alg...So lets sum up: <BR/>The argument that there are no algorithm people on the committee: false<BR/><BR/>The argument that algorithm papers are underrepresented in an unusual way: false<BR/><BR/>The argument that there are more FOCS/SODA rejected papers than usual: unverified and irrelevant<BR/><BR/>So, we are left with a blogger who, as mentioned before, enjoys being in disagreement with the rest of humanity. How exciting.<BR/><BR/>Of course, one could argue (and many do) that STOC/FOCS under represent some fields and over represent others. One could also argue that the acceptance standards are misguided. An effective discussion requires some maturity and civility => not on this blog.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6622508458240200392008-05-20T15:07:00.000-04:002008-05-20T15:07:00.000-04:00I think the distinction between approximation algo...I think the distinction between approximation algorithms and exact algorithms is much narrower than you imply, and failing to count them is strange. Fast optimal algorithms tend to use what I would ocnsider to be approximation techniques (cuttings in computational geometry, scaling in flows, etc). <BR/><BR/>Of course, you have the right to use the word algorithm in any way you see fit, but then you might be in a disagreement with the rest of humanity(*). An adimerable position to be in, but not necessarily benefitial for a discussion on a blog.<BR/><BR/><BR/>Humanity = people currently doing phd in theory of CS in MIT.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-27044637370472587122008-05-20T14:14:00.000-04:002008-05-20T14:14:00.000-04:00I guess I have my own definition of algorithms tha...I guess I have my own definition of algorithms that can include, for instance, streaming algorithms, but on the other hand does not include approximation algorithms (and thus does not include mechanism design, price of anarchy etc). <BR/><BR/>There are many reasons for this distiction. Perhaps the most important is that approximation algorithms are a big big field, which is very independent from the rest of algorithms. They use rather different techniques, and they are studied by a largely disjoint set of people.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-33143575096505783372008-05-20T14:07:00.000-04:002008-05-20T14:07:00.000-04:00Some of the algorithmic papers in STOC'08 (at leas...Some of the algorithmic papers in STOC'08 (at least, the titles suggest that they're algorithmic):<BR/><BR/>Minimum k-way cuts via deterministic greedy tree packing, Mikkel Thorup<BR/><BR/>Additive Guarantees for Degree Bounded Directed Network Design, Nikhil Bansal and Rohit Khandekar and Viswanath Nagarajan<BR/><BR/>Optimal Algorithms and Inapproximability Results For Every CSP? Prasad Raghavendra<BR/><BR/>A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem, Jianer Chen and Yang Liu and Songjian Lu and Barry O'Sullivan and Igor Razgon<BR/><BR/>Fast Integer Multiplication Using Modular Arithmetic, Anindya De and Piyush P Kurur and Chandan Saha and Ramprasad Saptharishi<BR/><BR/>Fast polynomial factorization and modular composition in small characteristic, Christopher Umans<BR/><BR/>An $O(\log^2 k)$-approximation algorithm for the $k$-vertex connected subgraph problem, Jittat Fakcharoenphol and Bundit Laekhanukit<BR/><BR/>Randomized Competitive Algorithms for Generalized Caching, Nikhil Bansal and Niv Buchbinder and Joseph (Seffi) Naor<BR/><BR/>Additive Approximation for Bounded Degree Survivable Network Design, Lap Chi Lau and Mohit Singh<BR/><BR/>Optimal Hierarchical Decompositions for Congestion Minimization in Networks, Harald Raecke<BR/><BR/>An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests, Ryan O'Donnell and Yi Wu<BR/><BR/>Optimal Algorithms for Finding Graphs, Sung-Soon Choi and Jeong Han Kim<BR/><BR/>Network Design for Vertex Connectivity, Tanmoy Chakraborty and Julia Chuzhoy and Sanjeev Khanna<BR/><BR/>Graph and Map Isomorphism and All Polyhedral Embeddings In Linear Time, Ken-ichi Kawarabayashi and Bojan Mohar<BR/><BR/>Faster Approximate Lossy Generalized Flow via Interior Point Algorithms, Samuel I. Daitch and Daniel A. Spielman<BR/><BR/>For sure there are more algorithmic papers, but I just went through the titles and took the most obvious ones.<BR/><BR/>I think, MIP is saying that certain special types of algorithmic papers are poorly represented, but I don't think that we don't see any algorithmic papers.<BR/><BR/>BTW I haven't seen many data structure papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-49103000089585286202008-05-20T14:03:00.000-04:002008-05-20T14:03:00.000-04:00If you read my original post, I said that by "algo...If you read my original post, I said that by "algorithms" I mean "non-approximation algorithms." As you point out, there's not much reason to decry the fate of approximation algorithms at this conference.<BR/><BR/>Depending on exactly what you mean by non-approximation algorithms, a list can look like the following:<BR/><BR/>Minimum k-way cuts via deterministic greedy tree packing<BR/>Mikkel Thorup<BR/><BR/>Fast Integer Multiplication Using Modular Arithmetic<BR/>Anindya De and Piyush P Kurur and Chandan Saha and Ramprasad Saptharishi<BR/><BR/>Graph Sparsification by Effective Resistances<BR/>Daniel Spielman and Nikhil Srivastava<BR/><BR/>Faster Approximate Lossy Generalized Flow via Interior Point Algorithms<BR/>Samuel I. Daitch and Daniel A. SpielmanMihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-58224497933698728652008-05-20T13:50:00.000-04:002008-05-20T13:50:00.000-04:00Why doesn't the writer of this blog compile such a...Why doesn't the writer of this blog compile such a list? It's him, after all, who is making the claim. Why not provide us with some evidence? B.t.w., the two best paper awards went to algorithm papers!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-44654677537157526152008-05-19T16:59:00.000-04:002008-05-19T16:59:00.000-04:00Just for the record: would someone compile a list ...Just for the record: would someone compile a list of algorithmic papers (whatever that means) at STOC 2008? It should not be such a huge task, since there is hardly any (according to mip).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-51817844907919298492008-05-19T13:26:00.000-04:002008-05-19T13:26:00.000-04:00I had one paper rejected from STOC, and I submitte...I had one paper rejected from STOC, and I submitted it to FOCS. Evidently I consider whatever decision that STOC PC reached for algorithmic papers to be irrelevant, since they hardly accepted any. I guess the competition among algorithmic papers will higher than usual at this FOCS, since it has to take a double load...Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-86004784342447149712008-05-19T01:32:00.000-04:002008-05-19T01:32:00.000-04:00Where did you resubmit your rejected STOC papers? ...Where did you resubmit your rejected STOC papers? Surely not FOCS...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-77301080258396791842008-05-19T00:32:00.000-04:002008-05-19T00:32:00.000-04:00Still, with what confidence can you say "large num...Still, with what confidence can you say "large number of accepted rejects imply bad decisions by committee members"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-1347187872875533832008-05-18T22:52:00.000-04:002008-05-18T22:52:00.000-04:00The argument "they have to be published somewhere"...The argument "they have to be published somewhere" sounds a bit lame for the intended level of STOC/FOCS, don't you think? :)<BR/><BR/>Of course people resubmit. I'm sure most authors of those 15 papers had the best intentions. My qualms are not about them.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-46418639477484424802008-05-18T14:58:00.000-04:002008-05-18T14:58:00.000-04:00I think this is just a fact of life we have to acc...I think this is just a fact of life we have to accept. Maybe those 15 papers that got rejected were not excellent; but they do have to be published somewhere, don't they? If you've ever had a paper rejected, didn't you patch it up and send it in again (perhaps at another conference)? Do you think a rejection means the paper is dead? Do you think it should mean that?Anonymousnoreply@blogger.com