Recent Results on Index Coding

Professor Young-Han Kim
Professor, University of California, San Diego
Given on: Sept. 26th, 2013


Originally introduced to minimize the number of transmissions in satellite communication, 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, device-to-device relaying, and interference management. After reviewing the historical development of the index coding problem, I will present a new approach to the problem based on information-theoretic tools. Unlike the existing algebraic and combinatorial approaches, this approach leads to a powerful coding scheme that outperforms the best-known rate for a general index coding problem. In particular, this ‘‘composite coding’’ scheme achieves the capacity region for all 9608 index coding problems with five receivers.

Joint work with Fatemeh Arbabjolfaei (UCSD), Bernd Bandemer (Bosch), Eren Sasoglu (Berkeley), and Lele Wang (UCSD)


Young-Han Kim received his B.S. degree in Electrical Engineering from Seoul National University in 1996 and his Ph.D. degree in Electrical Engineering (M.S. degrees in Statistics and in Electrical Engineering) from Stanford University in 2006. Since then, he has been a faculty member in the Department of Electrical and Computer Engineering at the University of California, San Diego. Professor Kim is a recipient of the 2008 NSF CAREER Award and the 2012 IEEE Information Theory Paper Award. He is serving as a Distinguished Lecturer for the IEEE Information Theory Society for years 2012 and 2013.