On the capacity of information networks

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