Given a Boolean function $f:\left\{-1,1{\right\}}^{n}\to \left\{-1,1\right\}$ , the Fourier distribution assigns probability $\stackrel{^}{f}\left(S{\right)}^{2}$ to $S\subseteq \left[n\right]$ The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H\left({\stackrel{^}{f}}^{2}\right)\le CInf\left(f\right)$ where $H\left({\stackrel{^}{f}}^{2}\right)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf\left(f\right)$ is the total influence of $f$
1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if ${H}_{\mathrm{\infty }}\left({\stackrel{^}{f}}^{2}\right)\le CInf\left(f\right)$ , where ${H}_{\mathrm{\infty }}\left({\stackrel{^}{f}}^{2}\right)$ is the min-entropy of the Fourier distribution. We show ${H}_{\mathrm{\infty }}\left({\stackrel{^}{f}}^{2}\right)\le 2{C}_{min}^{\oplus }\left(f\right)$ , where ${C}_{min}^{\oplus }\left(f\right)$ is the minimum parity certificate complexity of $f$ . We also show that for every ε≥ $\epsilon \ge 0$ , we have ${H}_{\mathrm{\infty }}\left({\stackrel{^}{f}}^{2}\right)\le 2\mathrm{log}\left(‖\stackrel{^}{f}{‖}_{1,\epsilon }/\left(1-\epsilon \right)\right)$ , where $‖\stackrel{^}{f}{‖}_{1,\epsilon }$ is the approximate spectral norm of $f$ . As a corollary, we verify the FMEI conjecture for the class of read- $k$ $DNF$ s (for constant $k$ ).
2) We show that $H\left({\stackrel{^}{f}}^{2}\right)\le 2aU{C}^{\oplus }\left(f\right)$ , where $aU{C}^{\oplus }\left(f\right)$ is the average unambiguous parity certificate complexity of $f$ . This improves upon Chakraborty et al. An important consequence of the FEI conjecture is the long-standing Mansour's conjecture. We show that a weaker version of FEI already implies Mansour's conjecture: is $H\left({\stackrel{^}{f}}^{2}\right)\le Cmin\left\{{C}^{0}\left(f\right),{C}^{1}\left(f\right)\right\}$ ?, where ${C}^{0}\left(f\right),{C}^{1}\left(f\right)$ are the 0- and 1-certificate complexities of $f$ , respectively.
3) We study what FEI implies about the structure of polynomials that 1/3-approximate a Boolean function. We pose a conjecture (which is implied by FEI): no "flat" degree- $d$ polynomial of sparsity ${2}^{\omega \left(d\right)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.
arXiv.org e-Print archive
Algorithms and Complexity

Arunachalam, S, Chakraborty, S, Koucky, M, Saurabh, N, & de Wolf, R.M. (2018). Improved bounds on Fourier entropy and Min-entropy. arXiv.org e-Print archive.