The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions

Let \(X=(X_1,\ldots,X_n)\) be uniform on the Boolean cube, and let \(Y\) be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability \(p\). For a \(k\)-bit quantizer \(Q(X)\), reporting \(k\) input coordinates retains \(k(1-h_2(p))\) bits of inf