tag:blogger.com,1999:blog-3722233.post5232165705138952124..comments2024-04-20T13:30:48.050-05:00Comments on Computational Complexity: Max FlowLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-65358378241007940032012-09-17T14:13:43.270-05:002012-09-17T14:13:43.270-05:00@circle: Well, Orlin doesn't use fast matrix m...@circle: Well, Orlin doesn't use fast matrix multiplication to derive the O(mn) bound... admitted. But when analysing further possible improvements (the "or better" part of the paper), he does. ("relies on Williams' breakthrough" still may be a bit too provactive, though ...admitted, again.)fbahrhttps://www.blogger.com/profile/07700546880744044750noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36639060455049926902012-09-15T19:44:58.863-05:002012-09-15T19:44:58.863-05:00This is clearly not true: even a cursory reading o...This is clearly not true: even a cursory reading of the paper shows that the O(nm) result is not based in any way on fast matrix multiplication, much less on status of known bounds on ω. circenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4537190961903670562012-09-14T10:48:18.433-05:002012-09-14T10:48:18.433-05:00Evaluating the quality of papers is pretty hard fo...Evaluating the quality of papers is pretty hard for anyone who is not an expert on the particular topic. Conferences program committees have 3 reviewers, discussion, etc.. and still get it wrong sometime.<br /><br />So, the amount of blog chatter, or "simplicity" of the bound are not really markers of quality. There can be a paper that "merely" shaves a log factor, but crosses an important barrier and introduces new ideas.<br /><br />I am no max-flow expert so will not claim I can evaluate this work, but it seems the experts considered O(nm) to be the "right" bound for general max-cut without any constraints on the capacities (though it can be significantly improved when the ratio of capacities is at most polynomial, and perhaps the results of this paper for m=O(n) and prior works for m=Omega(n^2) show that you could shave another log n factor?). To quote the JACM 1998 paper of Goldberg and Rao: (which achieves O*(n^{2/3}m) for polynomial capacity ratio)<br /><br /><i>"The Omega(nm) bound is a natural barrier for maximum flow algorithms. In a path decomposition of a flow, the total path length is Theta(nm) in the worst case. This implies an Omega(nm) lower bound on algorithms which output explicit flow decomposition and on algorithms which augment flow one path at a time and, for each augmenting path, one arc at a time. This lower bound does not apply to algorithms that work with preflows or use data structures like dynamic trees [Sleator and Tarjan 1983] to manipulate flows. However, in spite of numerous attempts, no previous algorithm achieves this lower bound in general."</i><br /><br />Boaz Barak<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65482842756124671732012-09-14T09:33:32.807-05:002012-09-14T09:33:32.807-05:00That O(nm) is a nice function IS important since
...That O(nm) is a nice function IS important since <br />(and this is not rigorous) it could be tight, where as<br />something like O(nlog_{n/m} m) is not.<br /><br />Just speaking for me<br />Matrix Mult impressed me since it was open so long with very little progress.<br /><br />Max Flow impresses me since O(nm) is a nice function.<br /><br />(Perhaps I am easy to impress.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12300784959564705352012-09-14T03:48:03.709-05:002012-09-14T03:48:03.709-05:00Funnily enough, Jim Orlin's contribution relie...Funnily enough, Jim Orlin's contribution relies on Williams' "breakthrough" on fast matrix multiplication.<br />fbahrhttps://www.blogger.com/profile/07700546880744044750noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65529961892296214462012-09-13T23:16:54.560-05:002012-09-13T23:16:54.560-05:00I mentioned it on my blog after Suresh's tweet...I mentioned it on my blog after Suresh's tweet. <br /><br />I echo what I'm taking to be Jeff's confusion by your statements. There may be many reasons to like, or not like, Orlin's resut or Vassilevska Williams' matrix multiplication result. Both are improvements on long-standing results to very important problems, but the "gap" in your reaction to the two results isn't clear, and perhaps merits further explanation (if you feel like writing more about it).<br /><br />Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54321856716112599622012-09-13T17:43:08.959-05:002012-09-13T17:43:08.959-05:00it is really just another bound — Unlike a 0.001 r...<i>it is really just another bound</i> — Unlike a 0.001 reduction in the matrix multiplication exponent?JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.com