tag:blogger.com,1999:blog-3722233.post6573155776608981888..comments2023-03-23T09:50:46.959-05:00Comments on Computational Complexity: Barrier's for Matrx Mult Lower boundLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-16791731489646251082015-01-15T03:34:58.070-06:002015-01-15T03:34:58.070-06:00See the discussion in http://cstheory.stackexchang...See the discussion in http://cstheory.stackexchange.com/questions/9186/definition-of-matrix-multiplication-exponent-omegaArnabhttp://drona.csa.iisc.ernet.in/~arnabbnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49922180576067822852015-01-13T18:45:34.545-06:002015-01-13T18:45:34.545-06:00No post is complete without a spelling error: &quo...No post is complete without a spelling error: "routing" => "rooting"<br /><br />BTW, why shoot for exponent 2+\epsilon? Is it impossible for the exponent to be 2?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16443626400350963522015-01-13T12:23:55.491-06:002015-01-13T12:23:55.491-06:001) For instance, the LinBox package for linear alg...1) For instance, the LinBox package for linear algebra (in particular included in Sage) uses Strassen-Winograd's algorithm and even Bini's one. This recent paper (and its bibliography) gives some details: https://hal.archives-ouvertes.fr/hal-00987812/. <br /><br />2) Of course I am! (Easier to say that as an anonymous ;-)).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7077670816383016882015-01-13T10:23:57.548-06:002015-01-13T10:23:57.548-06:00I tend to think of the "+epsilon" as mea...I tend to think of the "+epsilon" as meaning "plus a little bit more that can't be zero and the smaller the epsilon is the larger the multiplicative constant the "O of" isn't showing becomes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10892628052810096682015-01-13T10:16:22.739-06:002015-01-13T10:16:22.739-06:00Good question- we sometimes are so used to how we ...Good question- we sometimes are so used to how we talk about things we forget that there are students out there who don't quite know the lingo yet.<br /><br />``We can multiply matrices in n^{2+epsilon}'' means<br /><br />for all \delta>0 there is an algorithm that will multiply matrices in time O(n^{2+\delta}).''<br /><br />so we can get as close to n^2 as we want, though the mult constant might grow--- it might<br />depend on delta. GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55934600826094418462015-01-13T09:49:40.895-06:002015-01-13T09:49:40.895-06:00For the sake of students like me - can someone bri...For the sake of students like me - can someone briefly spell out exactly what is meant by "2+epsilon"?<br /><br />Thanks in advance :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83530818868739260742015-01-13T09:25:02.005-06:002015-01-13T09:25:02.005-06:00(This is BIll Gasarch, I was in a diff gmail accou...(This is BIll Gasarch, I was in a diff gmail account when I responded)<br />1) I thought the O(n^3) alg was the one people usually used? Its a good question what is used usually- perhaps one could do a survey of linear algebra packages and see what is used most often.<br />2) Lets hope you're right!Anonymoushttps://www.blogger.com/profile/00496057724536630931noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48220180095313214062015-01-13T08:32:30.475-06:002015-01-13T08:32:30.475-06:00I am surprised by two parts of you post:
1. I wou...I am surprised by two parts of you post:<br /><br />1. I would not call the O(n³) algorithm the "usual" one, maybe the classical one or the schoolbook algorithm.<br /><br />2. "Alas the answer is prob no :-(": Of course, the barrier provided by the recent paper you mention shows that one needs new techniques to hope going down to O(n^(2+eps)), and especially in regards of the recent improvements of CW algorithm, I find this result remarkable. But since there has been several distinct techniques to attack MM over the years, I wouldn't be surprised at all if somebody brings a new technique to the domain!Anonymousnoreply@blogger.com