# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Improved Bounds on Fourier Entropy and Min-entropy

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1809.09819.pdf

(Preprint), 484KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arunachalam, S., Chakraborty, S., Koucký, M., Saurabh, N., & de Wolf, R. (2018). Improved Bounds on Fourier Entropy and Min-entropy. Retrieved from http://arxiv.org/abs/1809.09819.

Cite as: https://hdl.handle.net/21.11116/0000-0002-AA5A-A

##### Abstract

Given a Boolean function $f:\{-1,1\}^n\to \{-1,1\}$, the Fourier distribution

assigns probability $\widehat{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)\leq C Inf(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)\leq C Inf(f)$, where

$H_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show

$H_{\infty}(\hat{f}^2)\leq 2C_{\min}^\oplus(f)$, where $C_{\min}^\oplus(f)$ is

the minimum parity certificate complexity of $f$. We also show that for every

$\epsilon\geq 0$, we have $H_{\infty}(\hat{f}^2)\leq 2\log

(\|\hat{f}\|_{1,\epsilon}/(1-\epsilon))$, where $\|\hat{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(\hat{f}^2)\leq 2 aUC^\oplus(f)$, where $aUC^\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)\leq 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.

assigns probability $\widehat{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)\leq C Inf(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)\leq C Inf(f)$, where

$H_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show

$H_{\infty}(\hat{f}^2)\leq 2C_{\min}^\oplus(f)$, where $C_{\min}^\oplus(f)$ is

the minimum parity certificate complexity of $f$. We also show that for every

$\epsilon\geq 0$, we have $H_{\infty}(\hat{f}^2)\leq 2\log

(\|\hat{f}\|_{1,\epsilon}/(1-\epsilon))$, where $\|\hat{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(\hat{f}^2)\leq 2 aUC^\oplus(f)$, where $aUC^\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)\leq 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.