Lower Bounds for Multiplication via Network Coding

Understand

Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive.

• The best known upper bound, by F\"{u}rer, shows that two $n$-bit numbers can be multiplied via a boolean circuit of size $O(n \lg n \cdot 4^{\lg^*n})$, where $\lg^*n$ is the very slowly growing iterated logarithm.
• In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size $\Omega(n \lg n)$, thus almost completely settling the complexity of multiplication circuits.
• We additionally revisit classic conjectures in circuit complexity, due to Valiant, and show that the network coding conjecture also implies one of Valiant's conjectures.