On the most informative Boolean function under noise

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

1. Very close Groundwork for this paper Cited by this paper Not relevant

   The "Most informative boolean function" conjecture holds for high noise

   Alex Samorodnitsky · 2015 · arXiv.org · preprint, not peer reviewed · cited 9 times · Not summarized yet

   The high-noise proof establishes the Courtade–Kumar bound near crossover probability one-half, a partial result for the conjecture resolved here.

   Abstract

   We prove the "Most informative boolean function" conjecture of Courtade and Kumar for high noise $\epsilon \ge 1/2 - \delta$, for some absolute constant $\delta > 0$. Namely, if $X$ is uniformly distributed in $\{0,1\}^n$ and $Y$ is obtained by flipping each coordinate of $X$ independently with probability $\epsilon$, then, provided $\epsilon \ge 1/2 - \delta$, for any boolean function $f$ holds $I(f(X);Y) \le 1 - H(\epsilon)$. This conjecture was previously known to hold only for balanced functions.

2. Very close Another approach to the problem Cited by this paper Not relevant

   On the Most Informative Boolean Functions of the Very Noisy Channel

   Hengjie Yang, R. Wesel · 2018 · International Symposium on Information Theory · cited 7 times · Not summarized yet

   This paper uses a second-derivative argument to prove the conjecture in a dimension-dependent high-noise regime, rather than resolving it for every noise level.

   Abstract

   Let Xⁿ be a uniformly distributed n-dimensional binary vector, and Yⁿ be the result of passing Xⁿ through a binary symmetric channel (BSC) with crossover probability α. A recent conjecture postulated by Courtade and Kumar states that I(f(Xⁿ); Yⁿ) ≤ 1 − H(α). Although the conjecture has been proved to be true in the dimension-free high noise regime by Samorodnitsky, here we present a calculus-based approach to show a dimension-dependent result by examining the second derivative of H(α) − H(f(Xⁿ)|Yⁿ) at α = 1/2. Along the way, we show that the dictator function is the most informative function in the high noise regime…

3. Very close Same question Cited by this paper Not relevant

   Proof of the Most Informative Boolean Function Conjecture

   Mustafa Kesal · 2015 · arXiv.org · preprint, not peer reviewed · cited 8 times · Not summarized yet

   This paper also proves the Courtade–Kumar conjecture that no Boolean function reveals more about the noisy channel output than the stated coordinate benchmark.

   Abstract

   Suppose $\XX{N}$ is a uniformly distributed $N$-dimensional binary vector and $\YY{N}$ is obtained by passing $\XX{N}$ through a binary symmetric channel with crossover probability $\alpha$. Recently, Courtade and Kumar postulates that $I(f(\XX{N});\YY{N})\leq 1-\Be(\alpha)$ for any Boolean function $f$ \cite{courtade}. In this paper, we provide a proof of the correctness of this conjecture.

4. Very close Builds on this paper Cited by this paper Cites this paper Not relevant

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

   Hessam Mahdavifar, Ahmad Beirami · 2026 · arXiv.org · preprint, not peer reviewed · cited 6 times · Not summarized yet

   This paper proves the same one-bit conjecture in every dimension and extends the coordinate benchmark to multibit quantizers.

   Abstract

   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 information, making coordinate projections a natural quantization benchmark. For \(k=1\), this is the Courtade--Kumar conjecture: every Boolean function \(f\) satisfies \(I(f(X);Y)\leq 1-h_2(p)\), with equality for coordinate functions. We prove the conjecture in every dimension and for every crossover probability, without a balance assumption. The proof tracks the information gap relative to a coord…

5. Very close Groundwork for this paper Cited by this paper Not relevant

   Which Boolean functions are most informative?

   G. Kumar, T. Courtade · 2013 · 2013 IEEE International Symposium on Information Theory · cited 30 times · Not summarized yet

   This paper formulates the Courtade–Kumar conjecture and gives supporting evidence, while the present paper proves it.

   Abstract

   We introduce a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let Xⁿ be i.i.d. Bernoulli(l/2), and let Yⁿ be the result of passing Xⁿ through a memoryless binary symmetric channel with crossover probability α. For any Boolean function b : {0, l}ⁿ → {0,1}, we conjecture that I(b(Xⁿ);Yⁿ) ≤ 1 - H (α). While the conjecture remains open, we provide substantial evidence supporting its validity.

6. Close Another approach to the problem Cited by this paper Not relevant

   An improved upper bound for the most informative boolean function conjecture

   Or Ordentlich, Ofer Shayevitz, Omri Weinstein · 2015 · International Symposium on Information Theory · cited 23 times · Not summarized yet

   This paper derives an improved upper bound for balanced Boolean functions, rather than proving the conjectured bound for all functions.

   Abstract

   Suppose X is a uniformly distributed n-dimensional binary vector and Y is obtained by passing X through a binary symmetric channel with crossover probability α. A recent conjecture by Courtade and Kumar postulates that I(f(X); Y ) ≤ 1 - h(α) for any Boolean function f. So far, the best known upper bound was essentially I(f(X); Y ) ≤ (1 - 2α)2. In this paper, we derive a new upper bound that holds for all balanced functions, and improves upon the best known previous bound for α > 1 over 3.

7. Close Same question Cited by this paper Not relevant

   On the Courtade-Kumar conjecture for certain classes of Boolean functions

   Septimia Sârbu · 2017 · arXiv.org · preprint, not peer reviewed · cited 1 time · Not summarized yet

   This paper proves the Courtade–Kumar bound for certain classes of Boolean functions across dimensions and channel error probabilities.

   Abstract

   We prove the Courtade-Kumar conjecture, for certain classes of $n$-dimensional Boolean functions, $\forall n\geq 2$ and for all values of the error probability of the binary symmetric channel, $\forall 0 \leq p \leq \frac{1}{2}$. Let $\mathbf{X}=[X_1...X_n]$ be a vector of independent and identically distributed Bernoulli$(\frac{1}{2})$ random variables, which are the input to a memoryless binary symmetric channel, with the error probability in the interval $0 \leq p \leq \frac{1}{2}$, and $\mathbf{Y}=[Y_1...Y_n]$ the corresponding output. Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be an $n$-dimensional Boolean function. Then, the Courtade-Kumar conjecture states that the mutual information $\ope…

8. Close Same question Cited by this paper Not relevant

   The maximum mutual information between the output of a discrete symmetric channel and several classes of Boolean functions of its input

   Septimia Sârbu · 2017 · arXiv.org · preprint, not peer reviewed · cited 1 time · Not summarized yet

   This paper proves the same mutual-information bound for several classes of Boolean functions on binary symmetric channels.

   Abstract

   We prove the Courtade-Kumar conjecture, for several classes of n-dimensional Boolean functions, for all $n \geq 2$ and for all values of the error probability of the binary symmetric channel, $0 \leq p \leq 1/2$. This conjecture states that the mutual information between any Boolean function of an n-dimensional vector of independent and identically distributed inputs to a memoryless binary symmetric channel and the corresponding vector of outputs is upper-bounded by $1-\operatorname{H}(p)$, where $\operatorname{H}(p)$ represents the binary entropy function. That is, let $\mathbf{X}=[X_1 \ldots X_n]$ be a vector of independent and identically distributed Bernoulli(1/2) random variables, which…

Prior work it builds on

1. Related Broader context Not relevant

   The Courtade-Kumar Most Informative Boolean Function Conjecture and a Symmetrized Li-Médard Conjecture are Equivalent

   L. Barnes, Ayfer Özgür · 2020 · International Symposium on Information Theory · cited 12 times · Not summarized yet

   This paper relates the balanced-function Courtade–Kumar conjecture to a conjecture about noise-operator norms.

   Abstract

   We consider the Courtade-Kumar most informative Boolean function conjecture for balanced functions, as well as a conjecture by Li and Médard that dictatorship functions also maximize the Lα norm of Tpf for 1 ≤ α ≤ 2 where Tp is the noise operator and f is a balanced Boolean function. By using a result due to Laguerre from the 1880’s, we are able to bound how many times an Lα-norm related quantity can cross zero as a function of α, and show that these two conjectures are essentially equivalent.

2. Related Broader context Not relevant

   On the Optimality of Dictator Functions and Isoperimetric Inequalities on Boolean Hypercubes

   Zi-Jie Chen, Chandra Nair · 2024 · International Symposium on Information Theory · cited 10 times · Not summarized yet

   This paper studies dictator optimality for a family of entropy inequalities and connects them to the mutual-information conjecture.

   Abstract

   In this paper, we present a family of conjectures on the optimality of the dictator function among all Boolean functions for a new family of $\Phi$-entropies. Our main theorem shows that there is an ordering of these conjectures, in that if the conjecture is established for a value $\alpha$, then it holds for any $\beta$: $\beta\geq \alpha$ • For the parameter range $\frac{1}{2}\leq\alpha, \beta < 1$, this family of conjectures is stronger than the mutual information conjecture, originally proposed in a paper by Courtade and Kumar. By considering a limiting value of the noise parameter $\rho$, we show how these conjectures relate to isoperimetric inequalities on the Boolean Hypercube of a fl…

3. Related* Broader context Not relevant

   A Tight Upper Bound on the Mutual Information of Two Boolean Functions

   Georg Pichler, G. Matz, Pablo Piantanida · 2016 · Information Theory Workshop · cited 9 times · Not summarized yet

   The title indicates a mutual-information bound for pairs of Boolean functions, but no abstract is provided to specify its relationship further.

4. Related* Broader context Not relevant

   Which Boolean Functions Maximize Mutual Information on Noisy Inputs?

   T. Courtade, G. Kumar · 2014 · IEEE Transactions on Information Theory · cited 64 times · Not summarized yet

   The title concerns Boolean functions maximizing mutual information on noisy inputs, but no abstract is provided for a more specific comparison.

5. Related* Broader context Not relevant

   Local Optimality of Dictator Functions with Applications to Courtade-Kumar Conjecture

   Lei Yu · 2024 · arXiv.org · preprint, not peer reviewed · cited 1 time · Not summarized yet

   The title studies local optimality of dictator functions and its application to the Courtade–Kumar conjecture.