Title: Strong Functional Representation Lemma and Applications to Coding Theorems,
Abstract: 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$ bits. We use this strong functional
representation lemma (SFRL) to establish a bound on the rate needed for
one-shot exact channel simulation for general (discrete or continuous) random
variables, strengthening the results by Harsha et al. and Braverman and Garg,
and to establish new and simple 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.