SOURCE-LINKED INTELLIGENCE

Dimension Dependent Correlation Gap Bounds under Restricted Independence

arXiv · AI, language, vision and robotics · article · Sep 2, 2026 · UTC

The pairwise independent correlation gap is the ratio of the maximum expected value of a set function under arbitrary dependence to that under pairwise independence, measuring the loss from this independence restriction. Under mutual independence, this gap is universally bounded by $e/(e-1)$ for monotone submodular functions. With pairwise independence, a tighter $4/3$ upper bound was established for several special cases, including $n=3$, and conjectured to hold universally. A recent AI-assisted counterexample disproved this conjecture for $n=5$, leaving the validity of the $n=4$ bound and th

Read original source ↗ Open in workspace

recordType

paper

region

Global