Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-084 | 3rd June 2015 16:39

An Improved Upper Bound for the Most Informative Boolean Function Conjecture

RSS-Feed




Revision #2
Authors: Or Ordentlich, Ofer Shayevitz, Omri Weinstein
Accepted on: 3rd June 2015 16:39
Downloads: 1082
Keywords: 


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 $\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}$.



Changes to previous version:

In the previous version of this paper, we have presented Corollary 1 as a new result, and in addition we have proved that dictatorship is the optimal function for all $\alpha\in\left[0,\frac{2^{-2n}}{16n^2} \right]$. We are grateful to Thomas Courtade for bringing to our attention that (slightly weaker versions of) these results were already known, as partially discussed in Remark 1.


Revision #1 to TR15-084 | 3rd June 2015 16:35

An Improved Upper Bound for the Most Informative Boolean Function Conjecture





Revision #1
Authors: Or Ordentlich, Ofer Shayevitz, Omri Weinstein
Accepted on: 3rd June 2015 16:35
Downloads: 1081
Keywords: 


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 $\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}$.



Changes to previous version:

In the previous version of this paper, we have presented Corollary 1 as a new result, and in addition we have proved that dictatorship is the optimal function for all $\alpha\in\left[0,\tfrac{2^{-2n}}{16n^2} \right]$. We are grateful to Thomas Courtade for bringing to our attention that (slightly weaker versions of) these results were already known, as partially discussed in Remark 1.


Paper:

TR15-084 | 21st May 2015 03:01

Dictatorship is the Most Informative Balanced Function at the Extremes





TR15-084
Authors: Or Ordentlich, Ofer Shayevitz, Omri Weinstein
Publication: 21st May 2015 06:54
Downloads: 1339
Keywords: 


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 $\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}$.



ISSN 1433-8092 | Imprint