tag:blogger.com,1999:blog-6141980.post5594824203536829190..comments2024-03-20T12:28:35.004-05:00Comments on Nuit Blanche: Nobody Cares About You and Your AlgorithmIgorhttp://www.blogger.com/profile/17474880327699002140noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-6141980.post-73425441785311742092010-11-29T19:53:34.833-06:002010-11-29T19:53:34.833-06:00Another example, Lipton and Tarjan gave an O(n log...Another example, Lipton and Tarjan gave an O(n log n) algorithm that gives guaranteed approximation on large enough graph. Later, it was found that to for guarantee to be within half optimal, the graph needs at least 2^(2^400) nodes. (this is from Baker's "Approximation Algorithms") introYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-2213209468742387932010-11-29T19:52:07.690-06:002010-11-29T19:52:07.690-06:00This comment has been removed by the author.Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-31602039115085166942010-11-28T16:45:07.323-06:002010-11-28T16:45:07.323-06:00Oops. Thanks Yaroslav :-)Oops. Thanks Yaroslav :-)Igorhttps://www.blogger.com/profile/17474880327699002140noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-44566473220815219822010-11-27T20:44:29.741-06:002010-11-27T20:44:29.741-06:00Actually the exponent there is 0 Point 525, which ...Actually the exponent there is 0 Point 525, which isn't too bad. Comment on another post of his gives example of O(n^81) algorithm<br /><br />http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/#comment-7733Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-66885771282289807542010-11-27T03:07:22.166-06:002010-11-27T03:07:22.166-06:00subscribedsubscribedberoalhttps://www.blogger.com/profile/13229768366613602827noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-17140155555388463072010-11-27T03:04:00.440-06:002010-11-27T03:04:00.440-06:00I have hypothesized why this is the case. Scientis...I have hypothesized why this is the case. Scientists worship "novelty". Implementing an algorithm, provided its natural language description already exists, does not bring novelty, so is omitted in order to save resources of the scientist. Economic incentives.<br /><br />There is an interesting implication for what to do. If you are planning to punish an author, and no incentives from a third party exists, this will repel people. A reward is better, but what reward it may be…Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6141980.post-39816394211391699752010-11-25T13:44:31.060-06:002010-11-25T13:44:31.060-06:00Eric,
The worst is not the decoding part, it'...Eric, <br /><br />The worst is not the decoding part, it's the moment you figure out that the paper is wrong, misleading or a fraud (this has happened to me in a different field). On the one hand, you now know, on the other all the time spent is lost forever. <br /><br />Yaroslav,<br /><br />I can see where the TCS folks are coming from, while peers may give you some respect for a P result, people on the outside are likely to make fun of you if the polynomial exponent is 525 ( http://rjlipton.wordpress.com/2010/11/19/is-complexity-theory-on-the-brink/ ). <br /><br />Happy Thanksgiving to y'all.<br /><br />Igor.Igorhttps://www.blogger.com/profile/17474880327699002140noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-66260210131813665462010-11-25T12:45:20.625-06:002010-11-25T12:45:20.625-06:00You are lucky if the algorithm is even included in...You are lucky if the algorithm is even included in form of pseudo-code. Looking for graph theory algorithms I often come across papers which give algorithm in form of a high-level constructive proof of algorithms existence, with the task of turning it into set of instructions left to the reader. For instance "Algorithmic Graph Minor Theory" paper promises a polynomial time algorithm for certain graph theory problems, but you won't find any pseudo-code thereYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-37203289220615282072010-11-25T06:16:43.813-06:002010-11-25T06:16:43.813-06:00/concur
I can't tell you how many hours of m.../concur <br /><br />I can't tell you how many hours of my degree has been implementing other people's work so I can actually run meaningful comparisons :P<br /><br />Along with a PhD, I should get some kind of minor in "decoding" what the author *actually* implemented versus what they said in the abstract/intro/pseudo-code! :)Eric Tramelhttps://www.blogger.com/profile/04124904150449932990noreply@blogger.com