Computational Algebra Seminar: Harvey -- Integer multiplication is at least as hard as matrix transposition

Speaker: David Harvey (UNSW)
Title: Integer multiplication is at least as hard as matrix transposition
Time & Place: 15.00-16.00, Thursday 23 October, SMRI Seminar Room
Abstract:
It was recently proved that two $n$-bit integers may be
multiplied in $O(n \log n)$ steps on a multitape Turing machine. This
bound is believed to be optimal, but no lower bounds have been
established beyond the trivial $\Omega(n)$ bound. In a paper to be
presented at FOCS 2025 in Sydney later this year, Joris van der Hoeven
and I give a reduction from the \emph{transposition problem} for binary
matrices to the integer multiplication problem. There is a simple
folklore algorithm that transposes an $n \times n$ binary matrix in
time $O(n^2 \log n)$. Again, this is believed to be optimal, but no
proof is known. Our new reduction implies that if this transposition
algorithm is optimal, then integer multiplication satisfies the
expected $\Omega(n \log n)$ lower bound. In this talk I will give an
overview of how the reduction works.