The Encoding Complexity for Network Coding with 2 Simple Multicast Sessions

Dr. Kai CAI
Institute of Computing Technology, Chinese Academy of Sciences
Thursday, 24 March, 2011
11:00 am - 12:00 pm
Room 833, Ho Sin Hang Engineering Building The Chinese University of Hong Kong

The encoding complexity for network coding with one multicast sessions has been intensively studied but less understood for multiple sessions. We investigate the encoding complexity for 2 simple multicast sessions by using a region decomposition method and prove that: (1) A network coding solution can be obtained with time O(|E|); (2) Max{3, 2N-2} encoding links is sufficient to achieve a solution; and (3) A finite field of size max{2, √(2N-7/4) } is sufficient to achieve a solution, where |E| is the number of links and N is the number of sinks.


Kai Cai received his Ph.D. in mathematics from Peking University in 2004. He continued as a postdoctoral researcher at Tsinghua University from 2004 to 2006. He visited the Hong Kong University of Science and Technology from 2006 to 2007. After that, he joined the Institute of Computing Technology, Chinese Academy of Sciences. His research interest lies in Network coding, Sequences Design, Combinatorics, etc.