ECCC-Report TR04-034https://eccc.weizmann.ac.il/report/2004/034Comments and Revisions published for TR04-034en-usTue, 13 Apr 2004 17:31:31 +0300
Paper TR04-034
| Network Coding: Does the Model Need Tuning? |
April Rasala Lehman,
Eric Lehman
https://eccc.weizmann.ac.il/report/2004/034We consider the general network information flow problem, which was
introduced by Ahlswede et. al. We show a periodicity effect: for
every integer m greater than 1, there exists an instance of the
network information flow problem that admits a solution if and only if
the alphabet size is a perfect mth power. Building on this result, we
construct an instance with O(m) messages and O(m) nodes that admits a
solution if and only if the alphabet size is doubly exponential in m.
In other words, if we regard each message as a length-k bit string,
then k must be exponential in the size of the network. For this same
instance, we show that if edge capacities are slightly increased, then
there is a solution with a modest alphabet that has size only
exponential in m. In light of these results, we suggest that a more
appropriate model would assume that the network operates at slightly
under capacity.
Tue, 13 Apr 2004 17:31:31 +0300https://eccc.weizmann.ac.il/report/2004/034