Integer multiplication is at least as hard as matrix transposition

David Harvey, Joris van der Hoeven

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 mat…