TY - GEN
T1 - Integer multiplication is at least as hard as matrix transposition
AU - Harvey, David
AU - Hoeven, Joris Van Der
N1 - Publisher Copyright:
© 2025 IEEE.
PY - 2025/1/1
Y1 - 2025/1/1
N2 - 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 × n binary matrix requires Ω(n2 log n) steps on a Turing machine, then our reduction implies that multiplying n-bit integers requires Ω(n log n) steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected.
AB - 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 × n binary matrix requires Ω(n2 log n) steps on a Turing machine, then our reduction implies that multiplying n-bit integers requires Ω(n log n) steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected.
KW - integer multiplication
KW - lower bounds
KW - matrix transposition
UR - https://www.scopus.com/pages/publications/105034389806
U2 - 10.1109/FOCS63196.2025.00072
DO - 10.1109/FOCS63196.2025.00072
M3 - Conference contribution
AN - SCOPUS:105034389806
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1366
EP - 1381
BT - Proceedings - 2025 IEEE 66th Annual Symposium on Foundations of Computer Science, FOCS 2025
PB - IEEE Computer Society
T2 - 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025
Y2 - 14 December 2025 through 17 December 2025
ER -