Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Improved Bounds on Fourier Entropy and Min-entropy


Saurabh,  Nitin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 484KB

Supplementary Material (public)
There is no public supplementary material available

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
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.