AI & ML
Structure and Complexity of Perfect Functional Representations
arXiv math.IT0 views
arXiv:2611.25094v1 Announce Type: new 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.
Source:https://arxiv.org/abs/2611.25094PreviousThere is no binary linear $[65,9,29]$ codeNextGeneralized Covering radii and Deep Holes of a Family of Antiprimitive Narrow-Sense BCH Codes in Even Characteristic
Related posts
Hydra · Coeziune OM–IA — the complete DOI registry (2026-11-20): 8 published works
0dev.to OpenSource
Stop Renting Cloud GPUs & VPS: 4 Legitimate Free Compute Tiers in 2026 (Plus Billing Pitfalls)
0dev.to OpenSource
How to Decode a Wall of Wingdings Without a Key
0dev.to Programming
Beyond the Hype: How Modern Businesses Can Actually Benefit from AI Today
0dev.to Programming
How to Free Up Space on Android Without Deleting Anything
0dev.to Programming

All my git repos in one file: manage them day to day, rebuild them on a new machine
0dev.to Git