Institute of Electrical and Electronics Engineers, IEEE Transactions on Information Theory, 11(64), p. 6967-6978, 2018
2017 IEEE International Symposium on Information Theory (ISIT)
DOI: 10.1109/isit.2017.8006596
Full text: Download
This paper shows that for any random variables $X$ and $Y$, it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le\log(I(X;Y)+1)+4$. We use this strong functional representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding, multiple description coding and Gray-Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits. ; Comment: 14 pages