Index Coding: Fundamental Limits, Coding Schemes, and Structural Properties

Originally introduced to minimize the number of transmissions in satellite communication, index coding is a canonical problem in network information theory that studies the fundamental limit and optimal coding schemes for broadcasting multiple messages to receivers with different side information. The index coding problem provides a simple yet rich model for several important engineering problems in network communication, such as content broadcasting, peer-to-peer communication, distributed caching, device-to-device relaying, and interference management. It also has close relationships to network coding, distributed storage, and guessing games.This dissertation aims to provide a broad overview of this fascinating problem, focusing on the simplest form of unicast index coding.A unified view on coding schemes based on algebraic, graph-theoretic, and information-theoretic approaches is presented. Although the optimal communication rate, namely, the capacity is open in general, several bounds and structural properties are established. The relationships between index coding, distributed storage, and guessing game on directed graphs are also discussed