New Paper Proves Fundamental Limits on Polynomial Dependence Measures

A new paper by Yuqing Kong, 'The Algebraic Limits of Polynomial Information Measures,' explores the existence of polynomial functions that measure dependence between two random variables. Such functions must satisfy two properties: vanish when variables are independent, and obey the data processing inequality (DPI)—meaning dependence cannot increase under post-processing. Mutual information satisfies both but is transcendental, making unbiased estimation from finite samples impossible. A polynomial alternative would allow exact unbiased estimators, but this paper proves fundamental algebraic limits.

In the asymmetric case (different alphabet sizes, |X| > |Y|), no nonzero polynomial can simultaneously satisfy DPI on the larger side and vanish on independence. In the symmetric case (|X| = |Y| = n), any such polynomial must be divisible by the squared determinant of the joint distribution matrix, imposing a minimum degree of 2n. These results directly apply to multi-task peer prediction, where a principal incentivizes honest reports from agents observing correlated signals. Every mechanism running on ℓ tasks yields a polynomial measure of degree ℓ, so the lower bounds translate to requiring ℓ ≥ 2n tasks in symmetric settings, and no finite-task mechanism exists in asymmetric settings for the larger-alphabet side.