Correlation gaps under pairwise independence
Follow the latest progress by email.
For a nonnegative monotone submodular set function with fixed element marginals, compare the largest expected value over all joint distributions with the largest value over pairwise-independent distributions. Is their ratio always at most 4/3?
Why it matters and what counts as progress
Why it matters: The ratio measures how much restricting dependence can reduce the best achievable expected value.
What counts as progress: A universal upper bound, or an exact function and marginal vector whose two optimal values yield a ratio exceeding 4/3.
How the problem developed
- 2025 · Conjecture [1]
Arjun Ramachandra and Karthik Natarajan Introduced the pairwise-independent correlation gap and conjectured a universal 4/3 upper bound for nonnegative monotone submodular functions.
- 18 Jun 2026 · Counterexample [2]
Arjun Ramachandra and Karthik Natarajan with GPT-5.5 Pro assistance Gave a five-element coverage-function counterexample to the universal 4/3 conjecture.
AI contribution
Counterexample to a conjecture on the pairwise independent correlation gap using AI
A five-element coverage function with marginals (3/10, 7/20, 3/10, 7/20, 7/20) has ordinary concave closure 4 and pairwise-independent closure at most 479/160. Their ratio is at least 640/479, above the conjectured universal 4/3 bound.
Sources
Website timeline
Publication dates and editorial changes.
GPT-found example refutes a pairwise-independent correlation-gap bound