New paper proves the long-standing Courtade–Kumar conjecture with multibit extensions
abeirami · x · 2026-09-23
A new paper by Ahmad Beirami and co-author, "The Most Informative Bit and Beyond: A Proof of the Courtade–Kumar Conjecture and Multibit Extensions", resolves a long-open information theory problem.
- Setup: X is a uniform binary vector and Y is formed by independently flipping its bits; the goal is to compress X into k bits while preserving as much information about Y as possible.
- Natural benchmark: reporting k coordinates of X retains k[1−h₂(p)] bits of information.
- For k=1 this is the Courtade–Kumar conjecture: no one-bit function f(X) can be more informative about Y than a single coordinate of X. The paper proves the conjecture for every dimension and every noise level, without additional assumptions.
- The work also explores multibit extensions: whether coding can beat simply keeping part of the vector.
More from Research
- MatBrain splits reasoning from tool use: two models screen 30,000 crystal candidates in 48 hours — bravo_abad · 2026-09-23
- Scale AI launches SWE-Bench Pro V2, a harder agentic coding benchmark — bigblueboo · 2026-09-23
- If AI Writes All the Papers, Peer Review Becomes Humanity's Remaining Role — sudoraohacker · 2026-09-23
- Yarin Gal: I Ignore Papers Where the Candidate Isn't First or Last Author — yaringal · 2026-09-23
- New paper: Transferring the Intelligence of VLMs to Robotic Control — _akhaliq · 2026-09-23
- NTU UMM study: generation training boosts understanding in native multimodal models, but naive sharing conflicts — jiqizhixin · 2026-09-23