<p>In regards to (2), conditional super-linear lower bounds are known. A recent preprint by <a href="https://arxiv.org/abs/1902.10935" rel="nofollow noreferrer">Afshani, Freksen, Kamma, and Larsen</a> proves an <span class="math-container">$\Omega(n \log n)$</span> lower bound for the size of Boolean circuits computing integer multiplication, assuming a certain conjecture on network coding in undirected graphs. (See also <a href="https://rjlipton.wordpress.com/2019/04/30/network-coding-yields-lower-bounds/" rel="nofollow noreferrer">this blog post</a> and <a href="https://rjlipton.wordpress.com/2019/05/06/the-network-coding-conjecture-is-powerful/" rel="nofollow noreferrer">a follow-up post</a>.)</p>

<p>From the <a href="https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/21335#21335">linked post on major unsolved problems</a>, a super-linear lower bound <a href="https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/" rel="nofollow noreferrer">follows from the Heartmanis-Stearns conjecture</a>.</p>

CC BY-SA 4.0
2019-09-15T19:41:19.013Z
2019-09-15T19:41:19.013Z
Robert Andrews
<p>After millenia of quest we have identified two <span class="math-container">$n$</span> bit integers can be multiplied in <span class="math-container">$O(n\log n)$</span> time. Please refer details in <a href="https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/" rel="nofollow noreferrer">https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/</a>. The problem of placing multiplication in <span class="math-container">$O(n)$</span> time is <a href="https://cstheory.stackexchange.com/q/21335">still unsolved</a>.</p>

<ol>
<li><p>What evidence do we have that this can/cannot be brought to <span class="math-container">$O(n)$</span> time on uniform Turning model?</p></li>
<li><p>What evidence do we have that this can/cannot be brought to <span class="math-container">$O(n)$</span> complexity in a reasonable non-uniform model?</p></li>
</ol>

<cc.complexity-theory><circuit-complexity><time-complexity><turing-machines><complexity>
Evidence integer multiplication is in linear time?
Turbo
# Evidence integer multiplication is in linear time?

(Asked by: username_0 on 2019-09-15)

After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in <https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/>. The problem of placing multiplication in $O(n)$ time is [still unsolved](https://cstheory.stackexchange.com/q/21335).

1. What evidence do we have that this can/cannot be brought to $O(n)$ time on uniform Turning model?
2. What evidence do we have that this can/cannot be brought to $O(n)$ complexity in a reasonable non-uniform model?

**Tags:** cc.complexity-theory, circuit-complexity, time-complexity, turing-machines, complexity


---

## 1 answers

### Answer by username_1 on 2019-09-15. Score: 2 | Accepted answer

In regards to (2), conditional super-linear lower bounds are known. A recent preprint by [Afshani, Freksen, Kamma, and Larsen](https://arxiv.org/abs/1902.10935) proves an $\Omega(n \log n)$ lower bound for the size of Boolean circuits computing integer multiplication, assuming a certain conjecture on network coding in undirected graphs. (See also [this blog post](https://rjlipton.wordpress.com/2019/04/30/network-coding-yields-lower-bounds/) and [a follow-up post](https://rjlipton.wordpress.com/2019/05/06/the-network-coding-conjecture-is-powerful/).)

From the [linked post on major unsolved problems](https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/21335#21335), a super-linear lower bound [follows from the Heartmanis-Stearns conjecture](https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/).


---

