Courtade and Kumar's Coordinate-wise Mutual Information Question
The Courtade-Kumar conjecture (2014) posits that dictatorship functions maximize mutual information between a Boolean function's output and a noisy input. The paper resolves an open question posed by Courtade and Kumar themselves - a sharp bound of on the sum of coordinate-wise mutual informations for arbitrary bias - and extends the proven high-noise range of the main conjecture via optimal entropy bounds.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Boolean functions; information theory
- Posed by
- Thomas Courtade, Gowtham Kumar
- Year posed
- 2014
- Years open
- 12y
- Solved
- 2026-01-14
- Model
- Gemini Deep Think (larger internal version)
- Vendor
- Google DeepMind
- Collaborators
- Adel Javanmard, David P. Woodruff
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 22 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Fully resolves the posed coordinate-wise question; the main Courtade-Kumar conjecture itself remains open outside the extended high-noise range.
What the AI did
"The results in this paper were obtained with significant interaction with a larger version of Google's Deep Think Gemini-based model. The authors verified the entire paper and take full responsibility." The acknowledgments thank the Deep Think team by name.