The KKL theorem and Friedgut’s junta theorem - Analysis of Boolean Functions

A dictator was a single variable that dictates the function. A junta is a small set of variables that dictate the function.

We view

{- 1, 1}^{n}

as a graph, where a pair of vertices is connected by an edge if they differ in a single coordinate.

The edge boundary of a subset

A

of a graph is the set of edges with one vertex in

A

and one in

A^{c}

. We denote the edge boundary by

\partial A

Proof. Let $𝜃 A$ be the set of internal edges of $A$ – i.e. edges $a b$ with $a, b \in A$ . Then $n | A | = 2 | 𝜃 A | + | \partial A |$ , so the theorem is equivalent to showing that

| 𝜃 A | \leq \frac{1}{2} | A | \log_{2} | A |

for every $A$ .

Induction on $n$ . If $n = 1$ the result is true ( $3$ cases to check).

Let $A_{0} = {x \in A : x_{n} = 0}$ , $A_{1} = {x \in A : x_{n} = 1}$ . Then

| 𝜃 A | \leq | 𝜃 A_{0} | + | 𝜃 A_{1} | + \min {| A_{0} |, | A_{1} |} \leq \frac{1}{2} | A_{0} | \log_{2} | A_{0} | + \frac{1}{2} | A_{1} | \log_{2} | A_{1} | + \min {| A_{0} |, | A_{1} |}

by induction hypothesis. Want $\leq \frac{1}{2} (| A_{0} | + | A_{1} |) \log (| A_{0} | + | A_{1} |)$ . So it’s enough to prove

\frac{1}{2} x \log_{2} x + \frac{1}{2} y \log_{2} y + x \leq \frac{1}{2} (x + y) \log_{2} (x + y)

whenever $0 \leq x \leq y$ , or equivalently

x \log x + y \log y + 2 x \log 2 \leq (x + y) \log (x + y) .

If $x = y$ , we need

2 x \log x + 2 x \log 2 \leq 2 x \log (2 x),

which is indeed true.

Now differentiate with respect to $y$ . Left hand side becomes $\log y + 1$ , and right hand side becomes $\log (x + y) + 1$ . Since $x \geq 0$ , the left hand derivative is $\leq$ to the right hand derivative. □

Remark. If $| A | = 2^{n - 1}$ , this tells us that the edge-boundary is minimised by a half space. Let $f : {- 1, 1}^{n} \to {- 1, 1}$ be a function with $𝔼 f = 0$ , and therefore $Var f = 1$ . If $I (f) = 1$ , then $\sum_{A} | A | \hat{f} {(A)}^{2} = 1$ , but $\hat{f} (\emptyset) = 0$ and also $\sum_{A} \hat{f} {(A)}^{2} = 1$ by Parseval, so equality holds only if $f$ is linear, so $f$ is a dictator. Similarly, if equality almost holds, then by FKN $f$ is almost a dictator.

The above remark says that to minimise

I (f)

, the best thing is to have a dictator: just one variable contributing to

I (f)

. What if we forbid this, for example by asking that each variable has the same influence?

Might guess that taking majority vote is best for this, but as mentioned before this has

I (f) \approx \sqrt{n}

. It turns out the following is much better:

The “tribes” function of Ben–Or and Linial: Let

k, m \in ℕ

. Let

n = k m

, write

[n] = A_{0} \cup \dots \cup A_{i}

| A_{i} | = k

. Define

f (x) = 1

if and only if there exists

i

such that

x_{j} = 1

for every

j \in A_{i}

Proof. We shall obtain upper and lower bounds or $\sum_{i = 1}^{n} {Stab}_{\frac{1}{3}} (D_{i} f)$ (magical idea).

Upper bound: $\sum_{i} {Stab}_{\frac{1}{3}} (D_{i} f) \leq \sum_{i} ∥ D_{i} f ∥_{4 ∕ 3}^{2}$ . But $∥ D_{i} f ∥_{4 ∕ 3}^{4 ∕ 3} = {Inf}_{i} f$ , so

\sum_{i} ∥ D_{i} f ∥_{4 ∕ 3}^{2} = \sum_{i} {({Inf}_{i} f)}^{3 ∕ 2} \leq {(\max_{i} {Inf}_{i} f)}^{\frac{1}{2}} I (f) .

Lower bound: $\sum_{i} {Stab}_{\frac{1}{3}} (D_{i} f) = \sum_{i} \sum_{A} {(\frac{1}{3})}^{| A |} \hat{D_{i} f} {(A)}^{2}$ . But

\hat{D_{i} f} (A) = {\begin{matrix} \hat{f} (A \cup {i}) & i \notin A \\ 0 & i \in A \end{matrix}

(using the formula $\hat{D_{i} f} = \sum_{B ∋ i} \hat{f} (B) x_{B ∖ {i}}$ ). So

\begin{array}{l} \sum_{i} \sum_{A} {(\frac{1}{3})}^{| A |} \hat{D_{i} f} (A) & = \sum_{i} \sum_{A ∋ i} {(\frac{1}{3})}^{| A |} \hat{f} {(A \cup {i})}^{2} \\ = \sum_{B} {(\frac{1}{3})}^{| B | - 1} | B | \hat{f} {(B)}^{2} \\ \geq 3 Var f \sum_{B \neq \emptyset} {(\frac{1}{3})}^{| B |} \frac{\hat{f} {(B)}^{2}}{Var f} \end{array}

But

\sum_{B \neq \emptyset} \hat{f} {(B)}^{2} = ∥ f ∥_{2}^{2} - \hat{f} {(0)}^{2} = 𝔼 f^{2} - {(𝔼 f)}^{2} = Var f,

so $\sum_{B \neq \emptyset} \frac{\hat{f} {(B)}^{2}}{Var f} = 1$ .

The function $x \mapsto {(\frac{1}{3})}^{x}$ is convex, so by Jensen,

\sum_{B \neq \emptyset} {(\frac{1}{3})}^{| B |} \frac{\hat{f} {(B)}^{2}}{Var f} \geq {(\frac{1}{3})}^{\sum_{B \neq \emptyset} | B | \frac{\hat{f} {(B)}^{2}}{Var f}} = {(\frac{1}{3})}^{Ĩ (f)} .

Therefore,

{(\max_{i} {Inf}_{i} f)}^{\frac{1}{2}} I (f) \geq 3 Var f {(\frac{1}{3})}^{Ĩ (f)},

which rearranges to the result. □

Proof. If $Ĩ (f) \geq c \log n$ , then the result follows trivially by averaging.

Otherwise, by ?? 35, there exists $i$ such that ${Inf}_{i} (f) \geq \frac{9}{{(c \log n)}^{2}} \cdot 9^{- c \log n}$ . For small enough $c$ , that’s much bigger than $\frac{c \log n}{n}$ . □

This shows that the “tribes” example from last lecture is the best possible.

Motivation for why

Stab

is natural to define in order to tackle the The KKL theorem: We can assume

λ I (f) \leq c λ \log n

. Then

e^{λ I (f)} \leq n^{c λ}

. LHS is

e^{λ \sum_{A} | A | \hat{f} {(A)}^{2}}

, and by Jensen we get

\leq \sum_{A} \hat{f} {(A)}^{2} \cdot e^{λ | A |} = {Stab}_{e^{λ}} f

. So

Stab

comes up somewhat naturally.

Friedgut’s junta theorem states that a Boolean function with small total influence can be approximated by a

m

-junta for some small

m

The proof has some similarities with ?? 35, so we include less detail in this proof.

Proof. Let $τ > 0$ a constant to be chosen later and let

J = {i \in [n] : {Inf}_{i} f \geq τ} .

This time we estimate $\sum_{i \notin J} {Stab}_{\frac{1}{3}} (D_{i} f)$ .

\sum_{i \notin J} {Stab}_{\frac{1}{3}} (D_{i} f) \leq \sum_{i \notin J} {({Inf}_{i} f)}^{3 ∕ 2} \leq τ^{\frac{1}{2}} I (f) .

(The first inequality is proved using the same technique as in ?? 35.)

In the other direction,

\begin{array}{l} \sum_{i \notin J} {Stab}_{\frac{1}{3}} (D_{i} f) & = \sum_{i \notin J} {(\frac{1}{3})}^{| A |} \hat{f} {(A \cup {i})}^{2} \\ = 3 \sum_{B} | B ∖ J | {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \\ \geq 3 \sum_{B ⁄ \subset J} {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \end{array}

But

3 \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \geq 3 \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} {(\frac{1}{3})}^{k} \hat{f} {(B)}^{2} = {(\frac{1}{3})}^{k - 1} \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} \hat{f} {(B)}^{2} .

Let $g = \sum_{\begin{array}{c} B \subset J \\ | B | \leq k \end{array}} \hat{f} (A) x_{A}$ . Then

Then

∥ f - g ∥_{2}^{2} \leq \sum_{\begin{array}{c} A ⁄ \subset J \\ | A | \leq k \end{array}} \hat{f} {(A)}^{2} + \sum_{| A | > k} \hat{f} {(A)}^{2} .

By hypothesis,

\sum_{| A | > k} \hat{f} {(A)}^{2} = ∥ f^{(> k)} ∥_{2}^{2} \leq c .

But

3 \sum_{B ⁄ \subset J} | B ∖ J | {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \geq 3 \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} {(\frac{1}{3})}^{k} \hat{f} {(B)}^{2} = 3^{- (k - 1)} \sum_{\begin{array}{c} A ⁄ \subset J \\ | A | \leq k \end{array}} \hat{f} {(A)}^{2} .

\sum_{\begin{array}{c} A ⁄ \subset J \\ | A | \leq k \end{array}} \hat{f} {(A)}^{2} \leq 3^{k - 1} τ^{\frac{1}{2}} I (f) .

If we choose $τ = \frac{𝜀^{2}}{3^{2 k} I (f)}$ , then this is at most $𝜀$ , so $∥ f - g ∥_{2}^{2} \leq 2 𝜀$ . But $| J | \leq \frac{I (f)}{τ} = \frac{3^{2 k} I {(f)}^{3}}{𝜀^{2}}$ . □

Proof.

\begin{array}{l} I (f) & = \sum_{A} | A | \hat{f} {(A)}^{2} \\ \geq \sum_{| A | > k} | A | \hat{f} {(A)}^{2} \\ \geq k ∥ f^{(> k)} ∥_{2}^{2} \end{array}

So if $k \geq \frac{I (f)}{𝜀}$ , then $∥ f^{(\leq k)} ∥_{2}^{2} \geq 1 - 𝜀$ . By Theorem 5.5 we get a junta with $m \leq 3^{2 \frac{I (f)}{𝜀}} \cdot \frac{I {(f)}^{3}}{𝜀^{2}} = \exp (O (\frac{I (f)}{𝜀}))$ . □

Remark. Let $f : {- 1, 1}^{n} \to {- 1, 1}$ , $g : {- 1, 1}^{n} \to ℝ$ and suppose that $∥ f - g ∥_{2}^{2} \leq 𝜀$ . Let

h (x) = {\begin{matrix} 1 & g (x) \geq 0 \\ - 1 & g (x) < 0 \end{matrix}

Then if $h (x) \neq f (x)$ , then $g (x)$ has a different sign from $f (x)$ , so $| g (x) - f (x) |^{2} \geq 1$ . Since $𝔼 | f (x) - g (x) |^{2} \leq 𝜀$ , we have $ℙ [f (x) \neq h (x)] \leq 𝜀$ .

In other words, we can find a Boolean function that approximates $f$ , and if $g$ is a $J$ -junta, then so is $h$ .

5 The KKL theorem and Friedgut’s junta theorem