The common randomness capacity of a network of discrete memoryless channels
Open Access
- 1 March 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 46 (2) , 367-387
- https://doi.org/10.1109/18.825797
Abstract
We generalize our previous results on generating common randomness at two terminals to a situation where any finite number of agents, interconnected by an arbitrary network of independent, point-to-point, discrete memoryless channels, wish to generate common randomness by interactive communication over the network. Our main result is an exact characterization of the common randomness capacity of such a network, i.e., the maximum number of bits of randomness that all the agents can agree on per step of communication. As a by-product, we also obtain a purely combinatorial result, viz., a characterization of (the incidence vectors of) the spanning arborescences rooted at a specified vertex in a digraph, and having exactly one edge exiting the root, as precisely the extreme points of a certain unbounded convex polyhedron, described by a system of linear inequalitiesKeywords
This publication has 17 references indexed in Scilit:
- Common randomness in information theory and cryptography. II. CR capacityIEEE Transactions on Information Theory, 1998
- Secret key agreement by public discussion from common informationIEEE Transactions on Information Theory, 1993
- Perfect cryptographic security from partially independent channelsPublished by Association for Computing Machinery (ACM) ,1991
- On identification via multiway channels with feedbackIEEE Transactions on Information Theory, 1991
- Identification via channelsIEEE Transactions on Information Theory, 1989
- Identification in the presence of feedback-a discovery of new capacity formulasIEEE Transactions on Information Theory, 1989
- The capacity of the arbitrarily varying channel revisited: positivity, constraintsIEEE Transactions on Information Theory, 1988
- Report of the Session on Polyhedral Aspects of Discrete OptimizationAnnals of Discrete Mathematics, 1979
- Packing rooted directed cuts in a weighted directed graphMathematical Programming, 1974
- Blocking and anti-blocking pairs of polyhedraMathematical Programming, 1971