Improved bounds on Fourier entropy and Min-entropy

Abstract

Given a Boolean function $f:\{-1,1{\}}^n\to \{-1,1\}$, the Fourier distribution assigns probability $\hat{f}(S{)}^2$ to $S\subseteq [n]$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H({\hat{f}}^2)\le CInf(f)$, where $H({\hat{f}}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf(f)$ is the total influence of $f$. 1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if $H_{\infty }({\hat{f}}^2)\le CInf(f)$, where $H_{\infty }({\hat{f}}^2)$ is the min-entropy of the Fourier distribution. We show $H_{\infty }({\hat{f}}^2)\le 2C_{\min }^{\oplus }(f)$, where $C_{\min }^{\oplus }(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $\epsilon \ge 0$, we have $H_{\infty }({\hat{f}}^2)\le 2\log (\Vert \hat{f}{\Vert }_{1,\epsilon }/(1-\epsilon ))$, where $\Vert \hat{f}{\Vert }_{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({\hat{f}}^2)\le 2aU{C}^{\oplus }(f)$, where $aU{C}^{\oplus }(f)$ 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({\hat{f}}^2)\le C\min \{C^0(f),C^1(f)\}$?, where $C^0(f),C^1(f)$ 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 (d)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.

38 pages, arxiv abstract shortened to fit within the size limit