A new bound for the Fourier-Entropy-Influence conjecture

Abstract

In this paper, we prove that the Fourier entropy of an $n$-dimensional boolean function $f$ can be upper-bounded by $O(I(f)+\sum _{k\in [n]}{I}_k(f)\log \frac{1}{I_k(f)})$, where $I(f)$ is its total influence and $I_k(f)$ is the influence of the $k$-th coordinate. The proof is elementary and uses iterative bounds on moments of Fourier coefficients over different levels.

v2 includes a Note added mentioning related prior work [22]