Lecture 0: Introduction to Network Coding Theory

The network coding problem asks whether data throughput or completion time in a network can be improved by allowing coding, rather than treating bits as indivisible commodities in a flow. A seminal work by Ahlswede et al. (2000) showed that in the single-source multicast setting, the exact optimal throughput can always be achieved by coding. Since then, network coding has grown into a vast research area with over ten thousand papers. In 2019, Afshani et al. showed that the famous Network Coding Conjecture [Li and Li ’04] would imply a tight Omega(n log n) lower bound for integer multiplication. More recently, there has been a surge of theoretical works connecting network coding to other areas: graph algorithms [Haeupler Wajc Zuzic ’20, Akmal Jin ’24], locally decodable codes [Braverman He ’25], and distributed computing and information security [Hilton Parter Yogev ’22, Parter ’23]. In this Lecture 0, we motivate network coding from a theoretical perspective by presenting the reduction of Afshani et al. (2019) and a precursor of Parter (2023), which can already be seen in Jain (2004).