hide
Free keywords:
Computer Science, Computational Complexity, cs.CC
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.
