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

Your guide to containers at AWS re:Invent 2026
0AWS Containers Blog

Three Asian forwarders, one corridor: what Nippon Express, Yusen and CJ Logistics actually publish
0dev.to Data
Tương quan số liệu Nice vs PSG: Phép thử phòng thủ tại Allianz Riviera
0dev.to Data
Jacksonville, Florida Property Listings Dataset (2026-11-04): 6534 Rows, Excel Spreadsheet
0dev.to Data
Tương quan phong độ Parma vs AS Roma: Bài toán kiểm soát hỏa lực đội khách
0dev.to Data
Schalke 04 chạm trán Stuttgart: Bài toán hiệu suất chuyển hóa tại VELTINS-Arena
0dev.to Data