{"id":"openai-math/Integer-multiplication-below-n-log-n","pdf":"https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026","tags":["algorithms","complexity-theory","integer-multiplication"],"score":0,"title":"Integer multiplication below n log n","domain":"Theoretical computer science","family":"109","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give a deterministic algorithm that multiplies two n -bit integers in $`O(n(\\lg n)^{1-\\kappa})`$ worst-case time, with $`\\kappa=2^{-182}`$, on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the $`n\\log n`$ optimality conjecture of Schönhage and Strassen in this model.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://blog.computationalcomplexity.org/2026/10/when-is-it-plausible-that-result-is.html#:~:text=INT%20MULT%20Improved%20Algorithms%20for%20Integer%20Multiplication","kind":"web","site":"blog.computationalcomplexity.org","text":"INT MULT Improved Algorithms for Integer Multiplication of two \\(n\\)-bit numbers. In 1971 Schonhage and Strassen conjectured that there is an algorithm for integer multiplication that takes \\(O(n\\log n)\\) bit operations. In 2019, Harvey and van der Hoeven proved this conjecture. Is there an…","added":"2026-11-03","title":"When is it plausible that a result is optimal?","author":"Bill Gasarch"}],"formalized":false,"family_title":"Integer multiplication below $`n\\log n`$"}