Structure and Complexity of Perfect Functional Representations
Abstract
For given random variables $(X,Y)$, functional representation lemma states that there exists a random variable $Z$ and a deterministic function $g$ such that $Y = g(X,Z)$, and $X$ is independent of $Z$. In other words, $Z$ captures all the information about $Y$ not contained in $X$. We refer to $Z$ as a `perfect functional representation' if it satisfies $I(Y;Z) = H(Y|X)$. We show that the existence of perfect representation depends solely on the conditional distribution $p_{Y|X}$ and define the corresponding conditional distributions as perfectly representable. We provide a necessary and sufficient condition for $p_{Y|X}$ to be perfectly representable. Moreover, we cast the problem of checking perfect representability as a linear program, give an algorithm whose complexity is polynomial in $|\mathcal Y|$ and exponential in $|\mathcal X|$, and prove that deciding perfect representability is NP-complete for rational input matrices encoded in binary.
- Comment
- 19 pages, 1 figure. Extended version of "On Perfect Functional Representations", presented at the 2026 IEEE International Symposium on Information Theory (ISIT) with complete proofs and additional results