Unveiling the Complexity of Multiplication and Sorting with Network Coding 🔍

Multiplication is one of the most fundamental computation problems, yet its true complexity remains elusive. For multiplication of two n-bit numbers, recent breakthrough work by Harvey and van der Hoeven (2019) gives a boolean circuit of size O(n log n). Is this optimal? In this talk, we answer the question affirmatively, conditioned on a widely believed conjecture in the seemingly completely unrelated area of network coding. The area of network coding studies the amount of bits that can be transmitted between different senders and receivers in a communication network with bandwidth constraints on the edges.