On the most informative Boolean function under noise

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

1. Très proche Même question Cité par cet article Pas pertinent

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

   Alex Samorodnitsky · 2015 · arXiv.org · preprint, non relu par les pairs · cité 9 fois · Pas encore résumé

   «The "Most informative boolean function" conjecture holds for high noise» étudie la conjecture de Courtade et Kumar dans le régime de bruit élevé, tandis que cet article la résout pour tout bruit.

   Résumé scientifique

   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. Très proche Autre approche du problème Cité par cet article Pas pertinent

   On the Most Informative Boolean Functions of the Very Noisy Channel

   Hengjie Yang, R. Wesel · 2018 · International Symposium on Information Theory · cité 7 fois · Pas encore résumé

   «On the Most Informative Boolean Functions of the Very Noisy Channel» traite la même conjecture en étudiant une dérivée seconde, pour un régime de bruit élevé dépendant de la dimension.

   Résumé scientifique

   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. Très proche Même question Cité par cet article Pas pertinent

   Proof of the Most Informative Boolean Function Conjecture

   Mustafa Kesal · 2015 · arXiv.org · preprint, non relu par les pairs · cité 8 fois · Pas encore résumé

   «Proof of the Most Informative Boolean Function Conjecture» affirme prouver la même borne de mutualité pour toute fonction booléenne.

   Résumé scientifique

   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. Très proche Prolonge cet article Cité par cet article Cite cet article Pas pertinent

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

   Hessam Mahdavifar, Ahmad Beirami · 2026 · arXiv.org · preprint, non relu par les pairs · cité 6 fois · Pas encore résumé

   «The Most Informative Bit and Beyond» reprend la conjecture résolue ici et étend l’étude aux quantificateurs à plusieurs bits.

   Résumé scientifique

   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. Très proche Base de cet article Cité par cet article Pas pertinent

   Which Boolean functions are most informative?

   G. Kumar, T. Courtade · 2013 · 2013 IEEE International Symposium on Information Theory · cité 30 fois · Pas encore résumé

   «Which Boolean functions are most informative?» formule la conjecture de Courtade et Kumar que cet article établit.

   Résumé scientifique

   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. Proche Même question Cité par cet article Pas pertinent

   An improved upper bound for the most informative boolean function conjecture

   Or Ordentlich, Ofer Shayevitz, Omri Weinstein · 2015 · International Symposium on Information Theory · cité 23 fois · Pas encore résumé

   «An improved upper bound» étudie la même conjecture, mais établit une nouvelle borne supérieure pour les fonctions équilibrées.

   Résumé scientifique

   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. Proche Même question Cité par cet article Pas pertinent

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

   Septimia Sârbu · 2017 · arXiv.org · preprint, non relu par les pairs · cité 1 fois · Pas encore résumé

   «On the Courtade-Kumar conjecture for certain classes of Boolean functions» prouve la conjecture pour certaines classes de fonctions, plutôt que pour toutes.

   Résumé scientifique

   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. Proche Même question Cité par cet article Pas pertinent

   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, non relu par les pairs · cité 1 fois · Pas encore résumé

   «The maximum mutual information» prouve la conjecture pour plusieurs classes de fonctions booléennes sur un canal symétrique discret.

   Résumé scientifique

   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…

Les travaux antérieurs sur lesquels il s’appuie

1. Apparenté Contexte plus large Pas pertinent

   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 · cité 12 fois · Pas encore résumé

   «The Courtade-Kumar Most Informative Boolean Function Conjecture and a Symmetrized Li-Médard Conjecture are Equivalent» relie cette conjecture à une conjecture sur les normes Lα de l’opérateur de bruit.

   Résumé scientifique

   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. Apparenté Contexte plus large Pas pertinent

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

   Zi-Jie Chen, Chandra Nair · 2024 · International Symposium on Information Theory · cité 10 fois · Pas encore résumé

   «On the Optimality of Dictator Functions and Isoperimetric Inequalities on Boolean Hypercubes» étudie l’optimalité des fonctions dictateur via des Φ-entropies et des inégalités isopérimétriques.

   Résumé scientifique

   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. Apparenté* Contexte plus large Pas pertinent

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

   Georg Pichler, G. Matz, Pablo Piantanida · 2016 · Information Theory Workshop · cité 9 fois · Pas encore résumé

   «A Tight Upper Bound on the Mutual Information of Two Boolean Functions» porte sur la mutualité entre fonctions booléennes, sans résumé permettant de préciser le lien.

4. Apparenté* Même question Pas pertinent

   Which Boolean Functions Maximize Mutual Information on Noisy Inputs?

   T. Courtade, G. Kumar · 2014 · IEEE Transactions on Information Theory · cité 64 fois · Pas encore résumé

   «Which Boolean Functions Maximize Mutual Information on Noisy Inputs?» porte sur la maximisation de l’information mutuelle de fonctions booléennes sur des entrées bruitées.

5. Apparenté* Contexte plus large Pas pertinent

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

   Lei Yu · 2024 · arXiv.org · preprint, non relu par les pairs · cité 1 fois · Pas encore résumé

   «Local Optimality of Dictator Functions with Applications to Courtade-Kumar Conjecture» examine l’optimalité locale des fonctions dictateur et ses applications à la conjecture.