Title：Network Coding in Planar Networks
Speaker：Prof. Zongpeng Li，University of Calgary, Canada
Time: 10:00am, Apr. 25, 2012
Venue: Room 305, Computer Science Building
Contact: Xin Wang xinw@fudan.edu.cn
======================================================================================
Abstract:
A basic problem in network coding is to choose a field to perform the encoding and decoding operations in. The main message we wish to deliver in this talk is that while unboundedly large fields are required in arbitrary networks, very small finite fields may be
sufficient for networks in practice. We use planar networks as a representative example of a practical network, which usually has a
linear number of links, and exhibits a topology close to a planar mesh. Focusing on a basic scenario of multicasting two source
information flows, we prove that coding over GF(3) is sufficient for all planar networks. We further show that GF(3) is also necessary, by constructing two new planar multicast networks, one of which is a bipartite, that require coding over GF(3) for achieving the maximum throughput. For the special case of outerplanar networks, we prove that network coding is always equivalent to routing. Our results also invite a renewed look at the choice of deterministic vs. randomized network coding in practical networks.
Bio:
Zongpeng Li received his B.E. degree in Computer Science and Technology from Tsinghua University (Beijing) in 1999, his M.S. degree in Computer Science from University of Toronto in 2001, and his Ph.D. degree in Electrical and Computer Engineering from University of Toronto in 2005. Since August 2005, he has been working at the Department of Computer Science in the University of Calgary, where he is currently an Associate Professor. His research interests are in computer networks, particularly in network optimization, multicast algorithm design, network game theory and network coding. Zongpeng was named an Edward S. Rogers Sr. Scholar in 2004, won the Alberta Ingenuity New Faculty Award in 2007, was nominated for the Alfred P. Sloan Research Fellow in 2007, and received the Best Paper Award at the Ninth Passive and Active Measurement Conference (PAM) in 2008.
