Technical Program

Paper Detail

Paper Title On the Most Informative Boolean Functions of the Very Noisy Channel
Paper IdentifierTU3.R9.3
Authors Hengjie Yang, Richard D. Wesel, University of California, Los Angeles, United States
Session Boolean Functions
Location Pontoise, Level 5
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 15:10 - 15:30
Manuscript  Click here to download the manuscript
Abstract Let $X^n$ be a uniformly distributed $n$-dimensional binary vector, and $Y^n$ be the result of passing $X^n$ through a binary symmetric channel (BSC) with crossover probability $\alpha$. A recent conjecture postulated by Courtade and Kumar states that $I(f(X^n);Y^n)\le 1-H(\alpha)$. 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(\alpha)-H(f(X^n)|Y^n)$ at $\alpha=1/2$. Along the way, we show that the dictator function is the most informative function in the high noise regime.