2018-09-26

# Improved bounds on Fourier entropy and Min-entropy

## Publication

### Publication

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}_{\mathrm{\infty}}({\hat{f}}^{2})\le CInf(f)$ , where ${H}_{\mathrm{\infty}}({\hat{f}}^{2})$ is the min-entropy of the Fourier distribution. We show ${H}_{\mathrm{\infty}}({\hat{f}}^{2})\le 2{C}_{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}_{\mathrm{\infty}}({\hat{f}}^{2})\le 2\mathrm{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 Cmin\{{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.

1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if ${H}_{\mathrm{\infty}}({\hat{f}}^{2})\le CInf(f)$ , where ${H}_{\mathrm{\infty}}({\hat{f}}^{2})$ is the min-entropy of the Fourier distribution. We show ${H}_{\mathrm{\infty}}({\hat{f}}^{2})\le 2{C}_{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}_{\mathrm{\infty}}({\hat{f}}^{2})\le 2\mathrm{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 Cmin\{{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.

Additional Metadata | |
---|---|

arXiv.org e-Print archive | |

Organisation | Algorithms and Complexity |

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