Allen–O’Donnell correlation-rounding conjecture

For every $n\in\mathbb{N}$ and every random vector $X=(X_1,\dots,X_n)\in\{\pm1\}^n$ , there is a universal constant $C>0$ such that, for every integer $t\ge1$ , one can condition on a set $S\subseteq[n]$ with $|S|\le Ct$ so that the remaining conditional correlations satisfy a bound of order $O(1/t)$ ; equivalently, the conditioning complexity required to make the relevant aggregate conditional-covariance quantity at most $\varepsilon$ is $O(1/\varepsilon)$ rather than the previously known $O(1/\varepsilon^2)$ . The conjecture is proved in the cited preprint for signed multivariate totally positive ( $\mathrm{MTP}_2$ ) laws, but remains open in general.

References

Primary source

arXiv

Additional references

MaxCut for MTP₂ Covariances — arXiv

Posted 4 weeks ago · edited 4 weeks ago

Progress summary

Refreshed 4 weeks ago

Claimed progress

A new unrefereed preprint settles the conjecture for a restricted family of dependent binary distributions, while the general case remains open.

The Allen–O’Donnell conjecture predicts an improved conditioning bound from $O(1/\epsilon^{2})$ to $O(1/\epsilon)$ , equivalently a conditional covariance bound of order $O(1/t)$ . Allen and Yuan Zhou posed it jointly; the general statement is not proved.

Known results

Allen, jointly with Yuan Zhou: the conjecture is proved for information-flow trees whose underlying tree is a caterpillar.
Allen: the homogeneous-star example rules out any general bound of $t=o(1/\epsilon)$ .

September 9, 2026: structured-class result

The preprint MaxCut for MTP $_2$ Covariances claims covariance and weighted covariance bounds for signed multivariate totally positive laws, implying the conjectured rounding behavior for that structured class. It is unrefereed.

Current status (as of September 2026): The conjecture is established for caterpillar information-flow trees and is claimed for signed $\mathrm{MTP}_2$ laws, but the general case remains open and the newest claim is unverified.

Sources

No solutions have been posted yet.