ECCC-Report TR14-141https://eccc.weizmann.ac.il/report/2014/141Comments and Revisions published for TR14-141en-usSat, 01 Nov 2014 08:40:37 +0200
Paper TR14-141
| Linear codes cannot approximate the network capacity within any constant factor |
Shachar Lovett
https://eccc.weizmann.ac.il/report/2014/141Network 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.
Sat, 01 Nov 2014 08:40:37 +0200https://eccc.weizmann.ac.il/report/2014/141