Matrix Multiplication Algorithms for Non-Square Matrices
There is an algorithm due to Coppersmith (later improved by him) that can multiply an $N \times N^\alpha$ matrix by an $N^\alpha \times N$ matrix in time $\tilde{O}(N^2)$ for some $\alpha &gt; 0$. The state of the art in this regard is a paper by Le Gall achieving a better $\alpha$, though his algorithm is much more complicated than Coppersmith's. Both algorithms are probably impractical. Ryan Williams (Appendix C) explains how to implement Coppersmith's algorithm, which a priori is non-uniform, in the context of a circuit lower bound; later it was shown that Coppersmith's algorithm can be replaced by other ingredients.