betaFeedback

WorksComputer Science

Structure and Complexity of Perfect Functional Representations

Abstract

For given random variables (X,Y)(X,Y), functional representation lemma states that there exists a random variable ZZ and a deterministic function gg such that Y=g(X,Z)Y = g(X,Z), and XX is independent of ZZ. In other words, ZZ captures all the information about YY not contained in XX. We refer to ZZ as a `perfect functional representation' if it satisfies I(Y;Z)=H(Y∣X)I(Y;Z) = H(Y|X). We show that the existence of perfect representation depends solely on the conditional distribution pY∣Xp_{Y|X} and define the corresponding conditional distributions as perfectly representable. We provide a necessary and sufficient condition for pY∣Xp_{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 ∣Y∣|\mathcal Y| and exponential in ∣X∣|\mathcal X|, and prove that deciding perfect representability is NP-complete for rational input matrices encoded in binary.

Paper details

vlnc:W_z5tzhar7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…