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
Trying to get our Arms around AI efficiency
0Stack Overflow Blog
Why an Embedded Game Fails on Some Phones, and How to Debug It
0dev.to
Microsoft 365 vs Office 2024: The Break-Even Math
0dev.to
Master AI Evals: Build Reliable, Scalable Model Evaluation Pipelines
0dev.to
What to give someone who misses a place
0dev.to
Google is pushing OEMs against GrapheneOS and bootloader unlocking
0Hacker News