Anna Blasiak
Department of Computer Science & Cornell University
Abstract:
Network coding theory studies the transmission of information in networks whose vertices may perform nontrivial encoding and decoding operations on data as it passes through the network. The central question in the area is to determine the amount by which coding can increase the rate of information flow as compared to transferring information without coding. Crucial to answering this question is developing tools to find upper bounds for the network coding rate.
One obstacle to solving the problem is that for graphs with cycles we do not know how to determine if a network code is “serializable,” meaning that it specifies a valid communication protocol free of cyclic dependencies among coding functions. A number of papers have given conditions implied by serializability that have led to upper bounds on certain graphs, but no one has given a necessary and sufficient condition. In this talk I will present a characterization of the constraint of serializability consisting of a polynomial-time algorithm that decides the serializability of a network code and a simple certificate that exists if and only if the graph is not serializable. Further, I will discuss a parameter called the “serializability deficit” of a network code, defined as the minimum number of extra bits that must be sent in order to make it serializable. I will show that for linear codes it is NP-hard to approximate this parameter within a constant factor, and I will demonstrate some surprising facts about the behavior of this parameter under parallel composition of codes.