# Matrix multiplication in $O(n^2 \log n)$

I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read article but it's complicated and will takes too many time to read it, but if there is anyone who reads this article or knows about this algorithm, Is this true? and are you knowing about the base Idea of this to describe it a little.

Thanks in advance, I know it's a bit general question but, if I found it's good approach I'll going to learn details.

• I think that it is useful to understand your own question better. Are you looking for a sequential algorithm or a parallel algorithm? No sequential algorithms for matrix multiplication with time O(n^2 log n) are known, and the paper by Eve is a partial result toward such algorithms (I did not read the paper, I just skimmed it). If you care about parallel time, then parallel time O(log n) (assuming scalar addition and scalar multiplication in constant time) is standard and you can find explanation in e.g. the book Computational Complexity by Papadimitriou. Nov 27, 2010 at 16:18
• (1) Please edit your question so that it is clear that you are asking about sequential algorithms. (2) I realized that you added the tag [quantum-computing]. Please edit your question to explain the relation to quantum computing. (My guess is that your question is motivated by quantum computing, but your own explanation is far more useful than any guess.) Nov 27, 2010 at 17:03
• I'd recommend you delete this question first then, and then repost later if you find that you do have a question. Nov 27, 2010 at 17:21
• @Saeed: This issue has been discussed on the meta and currently this is the site's policy, if you want to discuss the policy use the meta. On the other hand, you can modify the question and avoid mentioning the paper to make it on-topic, e.g. modifying the question to become "what is the best known algorithm for matrix multiplication in model X?" and that would be on-topic. (side note: if you cannot verify correctness of an unpublished paper yourself and want to cite it, you should wait till it is peer-reviewed and published.) Nov 27, 2010 at 19:37
• Related discussion on Meta: Is it ok to ask about the correctness of preprints on crank-friendly topics? I am not claiming that everything written on that page will apply to this question, but it is at least closely related. Nov 27, 2010 at 19:42

• In the newest version of this paper in arxiv.org/abs/1612.04208, the author claims to find an $O(n^2\log^c{n})$ algorithm for matrix multiplication. Have you ever read it? Is it correct? Apr 22, 2021 at 9:55