Generalized Cut-Set Bounds for Broadcast Networks

Prof. Tie LIU
Department of Electrical and Computer Engineering, Texas A & M University, College Station
Thursday, 18 April, 2013
2:30 - 3:30 pm
Room 1009, William M. W. Wong Engineering Building, The Chinese University of Hong Kong

A broadcast network is a capaciated directed acyclic graph with all source messages collocated at a single source node. Broadcast networks are network coding models for content-delivery networks. A special class of broadcast networks, known as the combination networks, are network coding models for efficient and robust access of distributed/cloud storage systems.  

For broadcast networks, the standard cut-set bounds, which are known to be loose in general, are closely related to union as a specific set operation to combine the basic cuts of the network. In this talk, we present a new set of network coding bounds for general broadcast networks. These bounds combine the basic cuts of the network via a variety of set operations (not just the union) and are established via only the submodularity of the Shannon entropy. The tightness of these bounds are demonstrated via applications to several combination networks.  

This is a joint work with Amir Salimi and Shuguang (Robert) Cui, both from Texas A&M.




Tie Liu received his B.S. (1998) and M.S. (2000) degrees, both in Electrical Engineering, from Tsinghua University, Beijing, China and a second M.S. degree in Mathematics (2004) and Ph.D. degree in Electrical and Computer Engineering (2006) from the University of Illinois at Urbana-Champaign. Since August 2006 he has been with Texas A&M University, where he is currently an Associate Professor with the Department of Electrical and Computer Engineering. His primary research interest is in understanding the fundamental performance limits of communication and distributed storage systems via the lens of information theory.

Dr. Liu is a recipient of the M. E. Van Valkenburg Graduate Research Award (2006) from the University of Illinois at Urbana-Champaign and the Faculty Early Career Development (CAREER) Award (2009) from the National Science Foundation.