Integer multiplication below n log n: a conditional witness kappa = 6685733/10^10 (> 2^-11) for T(n) = O(n (log n)^(1-kappa)) in the multitape model, building on OpenAI's problem and Colkitt's integer-mult-bounds: certificates, independent replays, Lean 4 checks
algorithms certificates mathematics fast-fourier-transform theoretical-computer-science interval-arithmetic formal-verification number-theoretic-transform computational-complexity open-problems complexity-theory lean4 multitape-turing-machine integer-multiplication fine-grained-complexity arithmetic-complexity
-
Updated
Oct 11, 2026 - Python