(2008-2011) Index Coding
My PhD project focused on the Index Coding with Side Information (ICSI) problem, which is a special case of the well-known Network Coding (NC) problem. An interesting fact is that the NC problem can also be reduced to the ICSI problem as long as the linear solvability of a network is concerned. Moreover, as a special case of non-multicast NC problem, some results established for ICSI improve those previously known for NC.
The ICSI problem studies the scenarios where a sender S wishes to send a vector of messages x = (x1, x2, … , xn) to a set of receivers R1, R2, … , Rm. Each receiver Ri requests exactly one message xf(i) and already knows a set of other messages xj’s, referred to as Ri’s side information. The task for S is to find the most efficient way to satisfy all requests simultaneously. The ICSI problem arises naturally in several scenarios, such as in audio/video-on-demand and in opportunistic wireless networks.
Together with my two co-authors, we made the following contributions to the study of the ICSI problem: (1) We investigated the families of ICSI instances where the most efficient solutions for S can be found in polynomial time; We also developed a dynamic programming algorithm to find the optimal solution (in polynomial time) for a particular family of ICSI instances; (2) We studied the security (and error correction) aspects of the ICSI problem, and in particular, we proved that the coset coding technique (which has been extensively used in the Network Coding literature to secure a network code) provides optimal secure solutions in the ICSI setting. Our work on the ICSI problem was presented in the following papers and manuscripts:
S. H. Dau and Y. M. Chee, "Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree Structures," Algorithmica, 2013.
S. H. Dau, V. Skachek, and Y. M. Chee, "Error Correction for Index Coding with Side Information," IEEE Transactions on Information Theory, vol. 59, no. 3, pp. 1517-1531, 2013.
S. H. Dau, V. Skachek, and Y. M. Chee, "On the Security of Index Coding with Side Information," IEEE Transactions on Information Theory, 58 (6), pp. 3975 – 3988, 2012.
S. H. Dau, V. Skachek, and Y. M. Chee, "Optimal index codes with near-extreme rates," in ISIT 2012 - Proceedings of the 2012 IEEE International Symposium on Information Theory, pp. 2251 – 2255.
S. H. Dau, V. Skachek, and Y. M. Chee, "Index coding and error correction," in ISIT 2011 - Proceedings of the 2011 IEEE International Symposium on Information Theory, pp. 1753 – 1757.
S. H. Dau, V. Skachek, and Y. M. Chee, "On secure index coding with side information," in ISIT 2011 - Proceedings of the 2011 IEEE International Symposium on Information Theory, pp. 1046 – 1050.