{"id":"arxiv/2609.02659","url":"https://arxiv.org/abs/2609.02659","tags":["math.PR","cs.LG","math.CO"],"score":0,"title":"Dimension Dependent Correlation Gap Bounds under Restricted Independence","domain":"math.PR","source":"arxiv","authors":["Arjun Ramachandra"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}