$$

The proof is due to Alex Samorodnitsky.¹

Let f be a boolean function with $\mathrm{Pr}[f=1]=\alpha$. Then $\mathrm{I}[f]\ge 2\alpha \log (1/\alpha )$,

This is significantly better than Poincaré’s inequality, which is only linear in $\alpha$ when $\alpha$ is small. In fact, it is perfectly tight: if $f$ is an AND of $i$ variables, then $\mathrm{Pr}[f=1]=2^{-i}$, and its total influence is $2i\cdot 2^{-i}=2\alpha \log (1/\alpha )$.

Method 1: entropy

Here, we will only show $\mathrm{I}[f]\ge H(\alpha )$, where $H(\alpha )$ is the binary entropy function. Since $H(\alpha )\ge \alpha \log (1/\alpha )$, this is only off by a factor $2$.

Intuition

Suppose you know $f(x)$, and you want to encode $x$ cheaply using this knowledge. It turns out that one optimal way to do this (which gets you the $H(\alpha )$ savings you deserve) is: for $i=1,\dots ,n$ encode $x_i$ according to the relative probability that $x_i=0$ and $x_i=1$, conditioned on the fact that you already know $f(x)$ and $x_1,\dots ,x_{i-1}$.

Now, if some for some $i$ you get big savings on average over all $x\in {\{0,1\}}^n$, this means that the proportion of $x_i=0$ and $x_i=1$ conditioned on $f(x)$ and $x_1,\dots ,x_{i-1}$ is usually pretty skewed to one side or another. This can only happen if ${\mathrm{Inf}}_i[f]$ is fairly high.² So this justifies intuitively that you’ll be able to lower bound $\sum _i{\mathrm{Inf}}_i[f]$ by something on the order of $H(\alpha )$ (the total savings from knowing $f(x)$ at the start).

Proof

Let $\mathit{X}$ be a uniformly random input. Let’s consider the quantity $\mathrm{H}[\mathit{X},f(\mathit{X})]$. On the one hand, $\mathrm{H}[\mathit{X},f(\mathit{X})]=\mathrm{H}[\mathit{X}]=n$. On the other hand,

$$\begin{array}{rl}\mathrm{H}[\mathit{X},f(\mathit{X})]& =\mathrm{H}[f(\mathit{X})]+\mathrm{H}[\mathit{X}\mid f(\mathit{X})]\\ & =H(\alpha )+\sum _{i=1}^n\mathrm{H}[{\mathit{X}}_i\mid {\mathit{X}}_{[i-1]},f(\mathit{X})]\\ & \ge H(\alpha )+\sum _{i=1}^n\mathrm{H}[{\mathit{X}}_i\mid {\mathit{X}}_{[n]\setminus \left\{i\right\}},f(\mathit{X})]\\ & =H(\alpha )+\sum _{i=1}^n(1-{\mathrm{Inf}}_i[f]).\end{array}$$

The result follows by rearrangement.

Method 2: entropy deficit

The intuition of this method is basically the same, except that instead of conditioning on $f(\mathit{X})$, we focus entirely on the values for which $f(x)=1$. We will show that the influences must “account for” the entropy deficit of $\log \frac{1}{\alpha }$.

Let $\mathit{Y}$ be uniform over $f^{-1}(1)$. Then $\mathrm{D}\left[\mathit{Y}\right]=\log \frac{1}{\alpha }$, and we can rewrite ${\mathrm{Inf}}_i[f]$ as

$${\mathrm{Inf}}_i[f]=2\alpha \cdot \mathrm{Pr}[f({\mathit{Y}}^{\oplus i})\ne 1]=2\alpha \cdot \mathrm{D}\left[{\mathit{Y}}_i\right|{\mathit{Y}}_{[n]\setminus \left\{i\right\}}].$$

Indeed,

• when $x\in f^{-1}(1)$ is sensitive in the $i^{\text{th}}$ direction, then ${\mathit{Y}}_{[n]\setminus \left\{i\right\}}=x_{[n]\setminus \left\{i\right\}}$ implies ${\mathit{Y}}_i=x_i$, which means the entropy deficit “is locally $1$”;
• when $x$ is not sensitive in the $i^{\text{th}}$ direction, then conditioned on ${\mathit{Y}}_{[n]\setminus \left\{i\right\}}=x_{[n]\setminus \left\{i\right\}}$, ${\mathit{Y}}_i$ is still uniform, which means the entropy deficit “is locally $0$”.

This means the edge-isoperimetric inequality is equivalent to

$$\sum _{i=1}^n\mathrm{D}\left[{\mathit{Y}}_i\right|{\mathit{Y}}_{[n]\setminus \left\{i\right\}}]\ge \mathrm{D}\left[\mathit{Y}\right].$$

Which is true because conditioning can only increase entropy deficit:

$$\begin{array}{rl}\sum _{i=1}^n\mathrm{D}\left[{\mathit{Y}}_i\right|{\mathit{Y}}_{[n]\setminus \left\{i\right\}}]& \ge \sum _{i=1}^n\mathrm{D}\left[{\mathit{Y}}_i\right|{\mathit{Y}}_{[i-1]}]\\ \text{(chain rule)}& & =\mathrm{D}\left[\mathit{Y}\right].\end{array}$$

1. It first appeared in “Lower bounds for linear locally decodable codes and private information retrieval” by Oded Goldreich, Howard Karloff, Leonard J. Schulman and Luca Trevisan. ↩

2. Note that this is basically the same argument as in the “janky proof” of Poincaré’s inequality. ↩