In the newest version of this paper by Yijie Han, the author claims that matrix multiplication can be solved by an $\tilde{O}(n^2)$ algorithm. It should be a big result, but it is still in arxiv and no one else ever cited it. I've tried to read it and the basic idea is an $O(\log^c{n})$ computation for inner product where $c$ is an constant, which results in an $O(n^2\log^c{n})$ algorithm for matrix multiplication.

The details in this paper are too complicated to be fully understand, have anyone checked the correctness of this paper or read this paper?

  • 3
    $\begingroup$ Probably people gave up. Notice that this paper 16 different versions and there was an error in each of the versions. Plus the paper seems to be poorly written, there are no lemmas inside etc. $\endgroup$ Apr 22 at 9:55
  • 1
    $\begingroup$ On page 20 of the current version, the author writes: "Also I have a vague feeling that the matrix multiplication algorithm presented in this paper may have implications to the NP-complete problems." $\endgroup$
    – Gamow
    Apr 22 at 10:53
  • $\begingroup$ Abstract states inner product in O(1) which means he is ignoring sizes of words. $\endgroup$
    – Mr.
    Apr 22 at 10:59
  • 1
    $\begingroup$ Current state of the art. $\endgroup$
    – J.G.
    Apr 28 at 11:58
  • 1
    $\begingroup$ @J.G. I knew the laser method but the Han's paper uses a totally different technology, which I have seen nowhere. $\endgroup$
    – Mengfan Ma
    Apr 28 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.