From secret key agreement to matroidal undirected network

摘要

An undirected network link model is formulated, generalizing the usual undirected graphical model. The optimal direction for multicasting can be found in polynomial time with respect to the size of the network, despite the exponential number of possible directions. A more general problem is considered where certain function of a distributed source is to be computed at multiple nodes. The converse results are derived, not from the usual cut-set bound but through the related problem of secret key agreement and secure source coding by public discussion. A unifying model of partly directed network is also formulated, covering both the directed and undirected networks as special cases.