Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We consider information networks in the absence of interference and noise, and present an upper bound on the rate at which information can be transmitted using network coding. Our upper bound is based on combining properties of entropy with a strong information inequality derived from the structure of the network.The undirected k-pairs conjecture states that the information capacity of an undirected network supporting k point-to-point connections is achievable by multicommodity flows. Our techniques prove the conjecture for a non-trivial class of graphs, and also yield the first known proof of a gap between the sparsity of an undirected graph and its capacity. We believe that these techniques may be instrumental in resolving the conjecture completely. We demonstrate the importance of the undirected k-pairs conjecture by connecting it with a long-standing open question in Input/Output (I/O) complexity. We also show that proving the conjecture would provide the strongest known lower bound for computation in the oblivious cell-probe model and give a non-trivial lower bound for two-tape oblivious Turing machines.Finally, we conclude by considering the capacity of directed information networks. We construct a family of directed graphs whose capacity is much larger than the rate achievable using only multicommodity flows. The gap that we exhibit is linear in the number of vertices, edges, and commodities of the graph, which is asymptotically optimal.

REFERENCES

• 1: Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335324]
• 2: A. Agarwal and M. Charikar. On the advantage of network coding for improving network throughput. In Proceedings of the IEEE Information Theory Workshop, Oct. 2004.
• 3: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 4: R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204--1216, July 2000.
• 5: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 6: László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
• 7: Paul Beame , Michael Saks , Xiaodong Sun , Erik Vee, Time-space trade-off lower bounds for randomized computation of decision problems, Journal of the ACM (JACM), v.50 n.2, p.154-195, March 2003 [doi>10.1145/636865.636867]
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: R. Dougherty, C. Freiling, and K. Zeger. Insufficiency of linear coding in network information flow. IEEE Transactions on Information Theory, 51(8), Aug. 2005.
• 10: Cynthia Dwork, Bounds on fundamental problems in parallel and distributed computation, 1983
• 11: R. Floyd. Permuting information in idealized two-level storage. In R. Miller and J. Thatcher, editors, Complexity of Computer Calculations, pages 105--109. Plenum, 1972.
• 12: M. T. Hajiaghayi and H. Räcke. An O(√n)-approximation algorithm for directed sparsest cut. Submitted Manuscript.
• 13: Nicholas J. A. Harvey , David R. Karger , Kazuo Murota, Deterministic network coding by matrix completion, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: N. J. A. Harvey, R. D. Kleinberg, and A. R. Lehman. Comparing network coding with multicommodity flow for the k-pairs communication problem. Technical Report 964, MIT LCS, September 2004.
• 15: T. Ho, R. Koetter, M. Médard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), June 2003.
• 16: S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 51(6), June 2005.
• 17: Kamal Jain , Mohammad Mahdian , Mohammad R. Salavatipour, Packing Steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 18: K. Jain, V. Vazirani, R. W. Yeung, and G. Yuval. On the capacity of multiple unicast sessions in undirected graphs. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Sept. 2005.
• 19: G. Kramer. Capacity results for the discrete memoryless network. IEEE Transactions on Information Theory, 49(1):4--21, Jan. 2003.
• 20: G. Kramer and S. Savari. Progressive d-separating edge set bounds on network coding rates. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Sept. 2005.
• 21: G. Kramer and S. A. Savari. On networks of two-way channels. In Proceedings of the DIMACS Workshop on Algebraic Coding Theory and Information Theory, Dec. 2003.
• 22: Lap Chi Lau, An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.61-70, October 17-19, 2004 [doi>10.1109/FOCS.2004.10]
• 23: April Rasala Lehman , Eric Lehman, Complexity classification of network information flow problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 24: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 25: Z. Li and B. Li. Network coding in undirected networks. In Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Mar. 2004.
• 26: Z. Li and B. Li. Network coding: The case of multiple unicast sessions. In Proceedings of the 42nd Allerton Annual Conference on Communication, Control, and Computing, Sept. 2004.
• 27: Z. Li, B. Li, D. Jiang, and L. C. Lau. On achieving throughput with network coding. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Mar. 2005.
• 28: Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979 [doi>10.1145/322123.322138]
• 29: S. Riis. Linear versus non-linear boolean functions in network flow. In Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Mar. 2004.
• 30: Michael Saks , Alex Samorodnitsky , Leonid Zosin, A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks, Combinatorica, v.24 n.3, p.525-530, July 2004 [doi>10.1007/s00493-004-0031-x]
• 31: L. Song, R. Yeung, and N. Cai. Zero-error network coding for acyclic networks. IEEE Transactions on Information Theory, 49:3129--3139, Dec. 2003.
• 32: Z. Zhang and R. W. Yeung. On characterization of entropy function via information inequalities. IEEE Transactions on Information Theory, 44(4), July 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

General Terms:
Algorithms, Design, Theory