Technical Program

Paper Detail

Paper Title A local perspective on the edge removal problem
Paper IdentifierMO2.R2.1
Authors Fei Wei, Michael Langberg, University at Buffalo, United States; Michelle Effros, California Institute of Technology, United States
Session Network Coding I
Location Saint Germain, Level 3
Session Time Monday, 08 July, 11:40 - 13:00
Presentation Time Monday, 08 July, 11:40 - 12:00
Manuscript  Click here to download the manuscript
Abstract The edge removal problem studies the loss in network coding rates that results when a network communication edge is removed from a given network. It is known, for example, that in networks restricted to linear coding schemes and networks restricted to Abelian group codes, removing an edge $e^*$ with capacity $R_{e^*}$ reduces the achievable rate on each source by no more than $R_{e^*}$. In this work, we seek to uncover larger families of encoding functions for which the edge removal statement holds. We take a {\em local} perspective: instead of requiring that all network encoding functions satisfy certain restrictions (e.g., linearity), we limit only the function carried on the removed edge $e^*$. Our central results give sufficient conditions on the function carried by edge $e^*$ in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once $e^*$ is removed.