ECCC-Report TR15-084https://eccc.weizmann.ac.il/report/2015/084Comments and Revisions published for TR15-084en-usWed, 03 Jun 2015 16:39:10 +0300
Revision 2
| An Improved Upper Bound for the Most Informative Boolean Function Conjecture |
Omri Weinstein,
Or Ordentlich,
Ofer Shayevitz
https://eccc.weizmann.ac.il/report/2015/084#revision2Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. So far, the best known upper bound was $I(f(X);Y)\leq (1-2\alpha)^2$.
In this paper, we derive a new upper bound that holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha<\frac{1}{2}$.
Wed, 03 Jun 2015 16:39:10 +0300https://eccc.weizmann.ac.il/report/2015/084#revision2
Revision 1
| An Improved Upper Bound for the Most Informative Boolean Function Conjecture |
Omri Weinstein,
Or Ordentlich,
Ofer Shayevitz
https://eccc.weizmann.ac.il/report/2015/084#revision1Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all $\alpha\in[0,\underline{\alpha}_n]$, and under the restriction to balanced functions, also for all $\alpha\in[\frac{1}{2}-\overline{\alpha}_n,\frac{1}{2}]$, where $\underline{\alpha}_n,\overline{\alpha}_n\to 0$ as $n\to\infty$. In addition, we derive an upper bound on $I(f(X);Y)$ which holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha<\frac{1}{2}$.Wed, 03 Jun 2015 16:35:17 +0300https://eccc.weizmann.ac.il/report/2015/084#revision1
Paper TR15-084
| Dictatorship is the Most Informative Balanced Function at the Extremes |
Omri Weinstein,
Or Ordentlich,
Ofer Shayevitz
https://eccc.weizmann.ac.il/report/2015/084Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all $\alpha\in[0,\underline{\alpha}_n]$, and under the restriction to balanced functions, also for all $\alpha\in[\frac{1}{2}-\overline{\alpha}_n,\frac{1}{2}]$, where $\underline{\alpha}_n,\overline{\alpha}_n\to 0$ as $n\to\infty$. In addition, we derive an upper bound on $I(f(X);Y)$ which holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha<\frac{1}{2}$.Thu, 21 May 2015 06:54:31 +0300https://eccc.weizmann.ac.il/report/2015/084