Alladi Ramakrishnan Hall

Improved Bounds on Fourier entropy and Min-entropy

Nitin Saurabh

MPII --> Technion

Given a Boolean function f : {-1,1}^n -> {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each subset S of [n] is sampled with probability equaling square of the Fourier coefficient associated with S, \hat{f}(S)^2. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai (1996) seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that H(f) <= C Inf(f), where H(f) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f.

We will discuss the significance of the conjecture, present new upper bounds on Fourier entropy of Boolean functions and also discuss its relationship with Mansour's conjecture.

This talk is based on a joint work with S. Arunachalam, S. Chakraborty, M. Koucky, and R. de Wolf.