We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding problems. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hypergraph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that this is a valid dual solution of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and nonlinear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known. provide bounds on the network coding rate, but the worstcase approximation factor of these bounds remains unknown. For example, it is known that there exists a network in which non-linear network coding can achieve a rate which exceeds the best linear network code by a factor of 11 10 [7], but it is not known whether this gap 1 can be improved to n 1−ε , or even possibly to Θ(n). In this paper we introduce a general technique for amplifying many of these gaps by combining linear programming with hypergraph product operations. For instance, this enables us to construct a family of network coding instances with n messages, in which the rate of the best non-linear network code exceeds the rate of the best (vector-)linear network code by a factor of at least n ε . A crucial ingredient in our technique is index coding [5], [4], a class of communication problems in which a server holds a set of messages that it wishes to broadcast over a noiseless channel to a set of receivers. Each receiver is interested in one of the messages and has side-information comprising some subset of the other messages. The objective is to devise an optimal encoding scheme (one minimizing the broadcast length) that allows all the receivers to retrieve their required information. Following [3], we use β to denote the limiting value of the information rate (i.e., ratio of broadcast length to message length) of this optimal scheme, as the message length tends to infinity. In our framework, index coding is most useful for isolating a sub-class of network coding problems that can be combined using lexicographic products. However, it is also an important and well-studied problem in its own right. Index coding is intimately related to network coding in general. It is essentially equivalent to the special case of network coding in which only one edge has finite capacity. 2 Additionally, [11] shows that linear network coding can be 1 The literature on network coding distinguishes between linear network codes, in which the messages are required to be elements of a finite field, and vector-linear network codes, in which the messages are elements of a finite-dimensional vector space over a finite field. Linear coding is weaker, and a gap of size n 1−ε is known [10] . Vector-linear coding is much more powerful, and no gap larger than 11/10 was known prior to our work. 2 The unique finite-capacity edge represents the broadcast channel. Each sender is connected to the tail of this edge, each receiver is connected to its head, and each receiver has incoming edges directly from a subset of the senders, representing the side-information.
Blasiak, Kleinberg, and Lubetzky REF demonstrated a class of networks whose capacities are larger than their linear capacities over any finite field by a factor that grows polynomially with the number of messages.
Lexicographic Products and the Power of Non-linear Network Coding
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
Mathematics Computer Science