Last night, a paper appeared on the arXiv titled A time matrix multiplication algorithm.

At first look the paper seemed to score zero on Scott Aaronson’s list of Ten Signs a Claimed Mathematical Breakthrough is Wrong, and it came from a researcher who has worked extensively on the related problem of all-pairs shortest path, so it looked exciting. Unfortunately, it actually scores one on Scott’s list: it contradicts known impossibility results. (Thanks to Yuval Filmus for the references.)

The first step in the algorithm is to show how to compute the inner product of two -dimensional vectors using multiplication. This contradicts a lower bound due to Pan (see here the proof of a more general result) that computing the inner product of two N-dimensional vectors require at least N multiplications.

In addition, Raz has proved an lower bound for matrix multiplication arithmetic circuits, and, to the best of my understanding, the paper’s claims imply an size arithmetic circuit. (Raz’s lower bound assumes that the circuit is not given access to large constants; as far as I can see, the formulas in Han’s paper do not require large constants.)