# Pairwise independent correlation gap

arXiv: https://arxiv.org/abs/2209.08563 · HTML: https://mlsanity.com/paper/2209.08563/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 18 references that are in the map.
- First posted on arXiv 18 Sep 2022.

## Builds on (most cited first, 3 of 3)

- [Stochastic Submodular Maximization: The Case of Coverage Functions](https://mlsanity.com/paper/1711.01566/) (2017)
- [Combinatorial Prophet Inequalities](https://mlsanity.com/paper/1611.00665/) (2016)
- [Tight Probability Bounds with Pairwise Independence](https://mlsanity.com/paper/2006.00516/) (2020)

## Built on by (most cited first, 1 of 1)

- [Dimension Dependent Correlation Gap Bounds under Restricted Independence](https://mlsanity.com/paper/2609.02659/) (2026)

## Abstract (arXiv)

In this paper, we introduce the notion of a ``pairwise independent correlation gap'' for set functions with random elements. The pairwise independent correlation gap is defined as the ratio of the maximum expected value of a set function with arbitrary dependence among the elements with fixed marginal probabilities to the maximum expected value with pairwise independent elements with the same marginal probabilities. We show that for any nonnegative monotone submodular set function defined on n elements, this ratio is upper bounded by 4/3 in the following two cases: (a) n = 3 for all marginal probabilities and (b) all n for small marginal probabilities (and similarly large marginal probabilities). This differs from the bound on the ``correlation gap'' which holds with mutual independence and showcases the fundamental difference between pairwise independence and mutual independence. We discuss the implication of the results with two examples and end the paper with a conjecture.