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

In this paper we present three new contributions towards the FEI conjecture:

1) We first consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [OWZ11,O'Donnell-book14] which asks if $\mathbb{H}_{\infty}(\hat{f}^2) \leq C\cdot Inf(f)$, where $\mathbb{H}_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $\mathbb{H}_{\infty}(\hat{f}^2)\leq 2 {C}_{\min}^\oplus(f)$, where ${C}_{\min}^\oplus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $\varepsilon\geq 0$, we have $\mathbb{H}_{\infty}(\hat{f}^2)\leq 2\log (\|\widehat{f}\|_{1,\varepsilon}/(1-\varepsilon))$, where $\|\widehat{f}\|_{1,\varepsilon}$ 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$). This improves upon a recent (independent) result of Shalev [Shalev18].

2) Our second contribution shows that $\mathbb{H}(\hat{f}^2)\leq 2 {aUC}^\oplus(f)$, where ${aUC}^\oplus(f)$ is the average unambiguous parity certificate complexity of $f$. This improves upon several bounds shown by Chakraborty et al. [CKLS16].

An important consequence of resolving the FEI conjecture is the long-standing conjecture of Mansour [Mansour95]. We show that a weaker question than the FEI conjecture would already imply Mansour's conjecture: is $\mathbb{H}(\hat{f}^2)\leq C\cdot \min\{{C}^0(f),{C}^1(f)\}$?, where ${C}^0(f)$ and ${C}^1(f)$ are the zero and one certificate complexities of $f$ respectively.

3) Our third contribution is to understand better an implication of the FEI conjecture relating to the structure of polynomials that $1/3$-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree $d$ and sparsity $2^{\omega(d)}$ can $1/3$-approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We finally discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.

Final version with minor updates.

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

In this paper we present three new contributions towards the FEI conjecture:

1) We first consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [OWZ11,O'Donnell-book14] which asks if $\mathbb{H}_{\infty}(\hat{f}^2) \leq C\cdot Inf(f)$, where $\mathbb{H}_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $\mathbb{H}_{\infty}(\hat{f}^2)\leq 2 {C}_{\min}^\oplus(f)$, where ${C}_{\min}^\oplus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $\varepsilon\geq 0$, we have $\mathbb{H}_{\infty}(\hat{f}^2)\leq 2\log (\|\widehat{f}\|_{1,\varepsilon}/(1-\varepsilon))$, where $\|\widehat{f}\|_{1,\varepsilon}$ 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$). This improves upon a recent (independent) result of Shalev [Shalev18].

2) Our second contribution shows that $\mathbb{H}(\hat{f}^2)\leq 2 {aUC}^\oplus(f)$, where ${aUC}^\oplus(f)$ is the average unambiguous parity certificate complexity of $f$. This improves upon several bounds shown by Chakraborty et al. [CKLS16].

An important consequence of resolving the FEI conjecture is the long-standing conjecture of Mansour [Mansour95]. We show that a weaker question than the FEI conjecture would already imply Mansour's conjecture: is $\mathbb{H}(\hat{f}^2)\leq C\cdot \min\{{C}^0(f),{C}^1(f)\}$?, where ${C}^0(f)$ and ${C}^1(f)$ are the zero and one certificate complexities of $f$ respectively.

3) Our third contribution is to understand better an implication of the FEI conjecture relating to the structure of polynomials that $1/3$-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree $d$ and sparsity $2^{\omega(d)}$ can $1/3$-approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We finally discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.