Some Thoughts About the Most Informative Boolean Function Conjecture

Wednesday, December 7, 2016 - 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Or Ordentlich



Building and Room Number

LIDS Lounge


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, where h(\cdot) is the binary entropy function. I will survey some of the progress done towards establishing this conjecture, which in general still remains open.