ECCC-Report TR18-167https://eccc.weizmann.ac.il/report/2018/167Comments and Revisions published for TR18-167en-usFri, 17 Sep 2021 09:20:50 +0300
Revision 1
| Improved bounds on Fourier entropy and Min-entropy |
Srinivasan Arunachalam,
Sourav Chakraborty,
Michal Koucky,
Nitin Saurabh,
Ronald de Wolf
https://eccc.weizmann.ac.il/report/2018/167#revision1Given 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.Fri, 17 Sep 2021 09:20:50 +0300https://eccc.weizmann.ac.il/report/2018/167#revision1
Paper TR18-167
| Improved bounds on Fourier entropy and Min-entropy |
Srinivasan Arunachalam,
Sourav Chakraborty,
Michal Koucky,
Nitin Saurabh,
Ronald de Wolf
https://eccc.weizmann.ac.il/report/2018/167Given 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.Sun, 07 Oct 2018 16:40:10 +0300https://eccc.weizmann.ac.il/report/2018/167