Integer multiplication is at least as hard as matrix transposition

Abstract

Working in the multitape Turing model, we show how to reduce the problem of matrix transposition to the problem of integer multiplication. If transposing an $n\times n$ binary matrix requires $\hat{I}\text{c◯}(n^2\log n)$ steps on a Turing machine, then our reduction implies that multiplying $n$-bit integers requires $\hat{I}\text{c◯}(n\log n)$ steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected.

28 pages