Fetching the paper…

Reading the bibliography…

2010

Mutual information, matroids and extremal dependencies

Abbe, Emmanuel

Original
PDF
Post on X

Understand

In this paper, it is shown that the rank function of a matroid can be represented by a "mutual information function" if and only if the matroid is binary.

The mutual information function considered is the one measuring the amount of information between the inputs (binary uniform) and the output of a multiple access channel (MAC).
Moreover, it is shown that a MAC whose mutual information function is integer valued is "equivalent" to a linear deterministic MAC, in the sense that it essentially contains at the output no more information than some linear forms of the inputs.
These notes put emphasis on the connection between mutual information functionals and rank functions in matroid theory, without assuming prior knowledge on these two subjects.

Mutual information, matroids and extremal dependencies · Around

Built on

R. Gallager, Information Theory and Reliable Communication , John Wiley & Sons, 1968
1968
Earlier work this paper cites.
S. Fujishije, Polymatroidal dependence structure of a set of random variables , Information and Control, vol. 39, pp. 55-72, 1978
1978
Earlier work this paper cites.
T. S. Han, A uniqueness of shannon’s information distance and related nonnegativity problems, J. Comb., Inform. Syst. Sci., vol. 6, no. 4, pp. 320-331, 1981
1981
Earlier work this paper cites.

Similar

L. Lovász, Submodular functions and convexity, in Mathematical Programming - The State of the Art, A. Bachem, M. Grötschel, and B. Korte, Eds. Berlin: Springer-Verlag, 1982, pp. 234-257
1982
Cited alongside, same era.
J. Oxley, Matroid Theory, Oxford Science Publications, New York, 1992
1992
Cited alongside, same era.
D. Tse and S. Hanly, Multi-access Fading Channels: Part I: Polymatroid Structure, Optimal Resource Allocation and Throughput Capacities, IEEE Trans. Inform. Theory, vol. IT-44, no. 7, pp. 2796-2815, November 1998
1998
Cited alongside, same era.
F. Matús̆, Probabilistic conditional independence structures and matroid theory: background, Int. J. of General Systems 22, pp. 185-196
Cited in the paper.
E. Şaşoğlu, private communications
Cited in the paper.

Then

Z. Zhang and R. Yeung, On characterization of entropy function via information inequalities, IEEE Trans. on Information Theory, vol. 44, no. 4, pp. 1140-1452, 1998
Original
1998
Later among the works it cites.
E. Abbe and E. Telatar, Polar codes for the m-user multiple access channel and matroids, International Zurich Seminar on Communications (IZS), Zurich, March 2010. Available on arXiv:1002.0777v1 [cs.IT]
Original
2010
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…