Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-141 | 24th October 2014 19:52

Linear codes cannot approximate the network capacity within any constant factor


Authors: Shachar Lovett
Publication: 1st November 2014 08:40
Downloads: 1955


Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation to date is by Dougherty et~al.~[IEEE Trans. Information Theory, 2005] who constructed a network with capacity $1$, where linear codes can achieve a rate of at most $10/11$.

We show that linear codes cannot approximate the capacity of a network within any constant factor. That is, for any $0<\alpha<1$ we construct a network with network capacity $1$, where linear codes can achieve a rate of at most $\alpha$. This is achieved by a new network composition operation, which allows to amplify bounds on the linear capacity of networks.

ISSN 1433-8092 | Imprint