tag:blogger.com,1999:blog-8890204.post3434961398825266297..comments2024-10-12T07:11:38.932-04:00Comments on My Biased Coin: SLOGNMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-8890204.post-36051820753183500922009-06-20T16:34:34.628-04:002009-06-20T16:34:34.628-04:00"I think if the algorithm is so unnatural tha..."I think if the algorithm is so unnatural that no one would consider implementing it or has prohibitively high O(1) constants it would be considered."<br /><br />I think though that amongst algorithmic results, only those which prove the existence of an algorithm with certain complexity, but is unable to explicitly describe them, would have a chance to be accepted. A proof that having an explicit description would imply that the either the Hodge conjecture or the GRH is false will seal the deal.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-4249672935760184732009-06-20T09:06:56.190-04:002009-06-20T09:06:56.190-04:00How are we supposed to submit? Does anyone know if...How are we supposed to submit? Does anyone know if they'll use easychair.<br /><br />Anon #5: I think if the algorithm is so unnatural that no one would consider implementing it or has prohibitively high O(1) constants it would be considered.Pall Melstedhttps://www.blogger.com/profile/04606222181560129813noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-37433149708967186832009-06-19T11:46:46.631-04:002009-06-19T11:46:46.631-04:00Previous winners of the SLOGN "Best Paper&quo...Previous winners of the SLOGN "Best Paper" award:<br /><br /><i>Proof Verification and the Hardness of Approximation Problems</i>, by S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, <b>54 pages</b>. "For shaving a sqrt(log n) factor off the query complexity in [AS92]."<br /><br /><i>Expander Flows, Geometric Embeddings and Graph Partitioning</i>, by S. Arora, S. Rao, U. Vazirani, <b>30 pages</b>. "For improving on the 16-year-old approximation ratio for Sparsest-Cut by a sqrt(log n) factor."<br /><br /><i>Triangulating a Simple Polygon in Linear Time</i>, by B. Chazelle, <b>40 pages</b>. "For shaving a log^*n factor off the previous best running time."<br /><br /><i>Free Bits, PCPs, and Non-Approximability -- Towards Tight Results</i>, by M. Bellare, O. Goldreich, M. Sudan, <b>113 pages</b>. "For the bound of 0.55218507 in Case 2.2.1.3 on page 66."<br /><br /><i>A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(sqrt{V} E) General Graph Matching Algorithm</i>, by V. Vazirani, <b>57 pages</b>. "For providing full details of the seminal fast matching algorithm of Micali and Vazirani."<br /><br /><i>The Complexity of Computing a Nash Equilibrium</i>, by C. Daskalakis, P. Goldberg, C. Papadimitriou, <b>70 pages</b>. "For pushing PPAD-completeness down from 4- to 3- to 2-player games."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-43605608371811698252009-06-18T20:32:19.449-04:002009-06-18T20:32:19.449-04:00To Anon 7:18pm, if any paper proposes an _algorith...To Anon 7:18pm, if any paper proposes an _algorithm_ then isn't that clearly a ground for its rejection? After all, can algorithms be deep mathematics?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-65037422653010346062009-06-18T19:41:37.467-04:002009-06-18T19:41:37.467-04:00I do not understand this sentiment against writing...I do not understand this sentiment against writing thirty page papers which uses deep mathematics. It should now be obvious to everyone that any paper settling or even making non-zero progress on the central questions of TCS (namely, those around the P/NP problem) will be considerably longer than thirty pages and will involve rather deep mathematics. While I understand that not everyone will want to work on such questions, I think it has suddenly become fashionable to uphold simplicity as a prime virtue, and technical mastery as some kind showmanship which should be exposed and vilified. Short simple-minded papers in TCS which contain little or no mathematics are usually mostly drivel.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-91183202754126181342009-06-18T19:18:01.038-04:002009-06-18T19:18:01.038-04:00It seems like you guys forgot one thing. If there ...It seems like you guys forgot one thing. If there is any mention of an experiment or implementation in the submission, then the submission would be immediately rejected. Of course, if they need to implement their algorithm or do any experiments, then the theory is not strong enough!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-68840659483679947312009-06-18T18:03:43.125-04:002009-06-18T18:03:43.125-04:00This sounded just right for the paper I am finishi...This sounded just right for the paper I am finishing up, all about shaving off a sublogarithmic factor. The location seems a bit inaccessible, though. :(Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-82883323328221960882009-06-18T16:47:34.904-04:002009-06-18T16:47:34.904-04:00Excellent !!Excellent !!Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.com