Dictator functions hold most information under binary noise
Dictators are most informative
Information Theory
Summary
When you take a string of bits (like 0s and 1s) and add random noise to them, you lose some information. The paper shows that if you want to guess a function of those bits that keeps the most information despite noise, you should pick a function that just looks at one bit (called a dictator function). This confirms a long-standing guess, the Courtade-Kumar conjecture. The authors proved this mathematically for all functions with inputs made of bits with values -1 or 1.
What this means in practice
- •For communication engineers: Design error-resilient systems that maximize information preservation for single-bit queries in noisy channels.
- •For data security teams: Identify system components where noise impacts data most to improve robustness by focusing on influential input bits.
A theory result. No direct application yet.
Authors
Vu Khac Ky, Tuan Tran
Abstract
We prove the Courtade-Kumar conjecture: among all Boolean functions $f\colon \{-1,1\}^n\to\{-1,1\}$, a dictator retains the most information about a uniformly random input observed through independent binary noise.