Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BINARY SYMMETRIC CHANNEL:
Reports tagged with Binary Symmetric Channel:
TR15-084 | 21st May 2015
Or Ordentlich, Ofer Shayevitz, Omri Weinstein

#### Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

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 ... more >>>

ISSN 1433-8092 | Imprint