Deterministic Network Coding by Matrix Completion

Опубликовано 6 сентября 2016, 5:15

Network coding is a new research area that centers on a fundamental and practical question: How much data can be transmitted through a communication network? Computer scientists have traditionally addressed such questions using network flow theory or other combinatorial models. Network coding enhances these traditional approaches by allowing network nodes to encode and intermingle the data as it flows through the network. It has been shown that the use of network coding can enable a higher transmission bandwidth, even if the transmitted data is incompressible.   In this talk, we consider the problem of constructing network codes for multicasting data. A algorithm for this problem was developed at MSR by Jaggi, Chou, Jain, et al., using graph theoretic methods. We present a new algorithm that is based on algebraic methods and matroid theory. Our main tool is a new deterministic algorithm for maximum-rank completion of mixed matrices---taking a matrix whose entries are a mixture of numeric values and symbolic variables, and assigning values to the variables so as to maximize the resulting matrix rank. Our algorithm is faster than existing deterministic algorithms and can operate over a smaller field. Finally, we discuss some results on the benefit of network coding for k-pairs communication problems, where there are several data sources and a single receiver for each source.