Dictators are most informative

Abstract

We prove the Courtade-Kumar conjecture: among all Boolean functions $f:\{-1,1{\}}^n\to \{-1,1\}$, a dictator retains the most information about a uniformly random input observed through independent binary noise.

36 pages