A Proof of the Most Informative Boolean Function Conjecture

Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff

Chen and colleagues prove that if XX is uniform on the Boolean cube and YY is obtained by independently flipping each coordinate with probability pp, every Boolean function gg satisfies I(g(X);Y)≤1−H2(p)I(g(X);Y)\le 1-H_2(p). Here H2H_2 is binary entropy. Reporting a single input coordinate attains equality.

What was already known

The authors build on an earlier differential-equation approach that reduced the problem to local inequalities. Mahdavifar and Beirami posted a separate proof in September 2026.

AI involvement AI-led

The authors credit the CUHK team with the Bellman function and a principal lower bound. Gemini led the split into parameter regions and developed many of the bounds and interval certificates. Google’s researchers directed the model work.

Importance Major

The proof settles the one-bit conjecture for arbitrary Boolean functions, including unbalanced ones, in every dimension.

Technical verification Formal (Lean)

The authors report an end-to-end Lean kernel check of the full theorem, with the main result collected in the pinned final check.

Formal checking

Checked the full one-bit theorem, including the computational certificates used in the argument.

Checker
Lean 4.33.1 kernel, as reported by Chen and colleagues
Scope
Chen and colleagues prove that if XX is uniform on the Boolean cube and YY is obtained by independently flipping each coordinate with probability pp, every Boolean function gg satisfies I(g(X);Y)≤1−H2(p)I(g(X);Y)\le 1-H_2(p). Here H2H_2 is binary entropy. Reporting a single input coordinate attains equality.
Basis
Reported by the linked checker

Human understanding Partial

The CUHK researchers explain how the Bellman function reduces the question to a finite-dimensional inequality. The paper credits the model with much of the subsequent regional argument.

Other useful sources

Correction and publication history