Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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