WorksComputer Science
Structure and Complexity of Perfect Functional Representations
Abstract
For given random variables , functional representation lemma states that there exists a random variable and a deterministic function such that , and is independent of . In other words, captures all the information about not contained in . We refer to as a `perfect functional representation' if it satisfies . We show that the existence of perfect representation depends solely on the conditional distribution and define the corresponding conditional distributions as perfectly representable. We provide a necessary and sufficient condition for 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 and exponential in , and prove that deciding perfect representability is NP-complete for rational input matrices encoded in binary.