The index coding problem, which lies at the intersection of many of the most fundamental problems in network information theory, has attracted much recent interest and has become a canonical open problem.
In this talk, we first consider the information theoretic optimality of the simplest achievable scheme, graph coloring. We will show that fractional coloring/clique covering/scheduling/TDMA/orthogonal access achieves the all-unicast capacity region of the index coding problem if and only if the bipartite network topology graph is chordal.
We will then identify the simplest index coding instance where non-Shannon information inequalities are necessary. Notably, our approach is by hand, from scratch, while all previous work on the necessity of non-Shannon inequalities relies on Vamos matroid or computer search.
Hua Sun received the B.E. degree in Communications Engineering from Beijing University of Posts and Telecommunications, Beijing, China, in 2011, the M.S. degree in Electrical and Computer Engineering from University of California, Irvine, in 2013. He is currently pursuing the Ph.D. degree at the University of California, Irvine. His research interests include information theory, index coding, networking and wireless communications.
