Integer multiplication below n log n
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.
Comments and reviews
No comments yet.
Discussed elsewhere
One of OpenAI's results is a deterministic algorithm for multiplying two $n$ -bit integers in time $$O(n (\log n)^{1-\varepsilon})$$ for a fixed $\varepsilon>0$ . This is especially startling because multiplication is one of the most fundamental operations in mathematics, and $n\log n$ was not…
Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log n)^{1-κ}) is governed by bounding the second moment E[X^2] < 1 of recursive branching processes over…
API
curl /api/v1/records/openai-math/Integer-multiplication-below-n-log-n
curl -X POST /api/v1/records/openai-math/Integer-multiplication-below-n-log-n/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Integer-multiplication-below-n-log-n/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Beyond n log n · Integer multiplicationbeyond-n-log-n.netlify.app
Conditional integer multiplication bounds, pull requests, mathematical approaches, and forks.