For every integer n≥ 1, every Boolean function f colon-1,1^n→-1,1, and every noise parameter rho∈[0,1], let X be uniformly distributed on -1,1^n, let Z_1,…,Z_n be independent random variables with P(Z_i=1)=(1+rho)/2 and P(Z_i=-1)=(1-rho)/2, independently of X, and define Y_i=X_iZ_i. Then I(f(X);Y)≤ 1-h_2((1-rho)/2), where I denotes mutual information and h_2(p)=-plog_2 p-(1-p)log_2(1-p). Equality is attained by a dictator function f(x)=x_j for some j∈1,…,n.

Courtade–Kumar conjecture

For every integer $n\ge 1$ , every Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ , and every noise parameter $\rho\in[0,1]$ , let $X$ be uniformly distributed on $\{-1,1\}^n$ , let $Z_1,\ldots,Z_n$ be independent random variables with $\mathbb{P}(Z_i=1)=(1+\rho)/2$ and $\mathbb{P}(Z_i=-1)=(1-\rho)/2$ , independently of $X$ , and define $Y_i=X_iZ_i$ . Then $I(f(X);Y)\le 1-h_2((1-\rho)/2)$ , where $I$ denotes mutual information and $h_2(p)=-p\log_2 p-(1-p)\log_2(1-p)$ . Equality is attained by a dictator function $f(x)=x_j$ for some $j\in\{1,\ldots,n\}$ .

References

Primary source

arXiv

Additional references

Dictators are most informative — arXiv — Vu Khac Ky, Tuan Tran

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

An unrefereed September 2026 preprint claims to settle the conjecture, but the proof has not yet been independently confirmed.

The Courtade–Kumar conjecture asserts that dictators maximize noisy information among Boolean functions on the discrete cube. Courtade and Kumar posed it in 2013; the newly announced work claims a proof in full generality.

Known results

Verified computationally in dimensions $n\le 7$ (2015 source describing the state of the problem).
Partial Fourier-analytic and stability results (2021).
Dictators proved locally optimal; computer-assisted proof of the balanced case for $\rho\in[0,0.914]$ (2024).

September 2026 claimed proof

On September 22, 2026, Vahab Mirrokni announced a claimed full proof and reported Lean verification of analytic parts; another announcement attributes a parallel approach to Sol/Astra. The cited arXiv preprint is unrefereed, and the retrieved evidence does not independently verify the proof.

Current status (as of September 2026): a full proof is claimed in new preprints, but the conjecture remains unverified; the earlier partial results are established.

Sources

No solutions have been posted yet.