## Analysis of Boolean Functions – Week 3

### Lecture 4

In the third week we moved directly to the course’s “punchline” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity.

Before that we  started with  a very nice discrete isoperimetric question on a graph which is very much related to the graph of the discrete cube.

Consider the graph G whose vertices are 0-1 vectors of length n with precisely r ‘1’s, and with edges corresponding to vertices of Hamming distance two. (Which is the minimal Hamming distance between distinct vertices.) Given a set A of m vertices, how small can $E(A, \bar A)$ be? (We already talked about intersecting families of sets of constant size – the Erdos-Ko-Rado theorem and, in general, it is a nice challenge to extend some of the ideas/methods of the course to constant weight situation.)

And now for the main part of the lecture.

1) Basics harmonic analysis on the discrete cube. We considered the vector space of real functions on the discrete cube $\Omega_n$ and defined an inner product structure. We also defined the p-th norm for $1\le p\le \infty$. Next we defined the Fourier-Walsh functions and showed that they form a orthonormal basis. This now leads to the Fourier-Walsh expansion for an arbitrary real function f on the discrete cube $f=\sum_{S\subset[n]}\hat f(S)W_S$, and we could easily verify Parseval formula.

2) Influence and Fourier. If f is a real function on $\Omega_n$ and $f=\sum \hat f(S)W_S$ its Fourier-Walsh expansion. We showed that $I_k(f)=\sum_{S:k \in S}\hat f^2(S)$. It follows that $I(f)=\sum_S\hat f^2(S)|S|$. The Fourier-theoretic proof for I(f) ≥ 4 t (1-t) where t=μ(f) now follows easily.

3) Chinchine, hypercontractivity and the discrete isoperimetric inequality.

Next we discussed what will it take to prove the better estimate I(f) ≥ K t log t. We stated Chinchine inequality, and explained why is Chinchine inequality relevant: For Boolean functions the pth power of the p-norm does not depend on p. (It always equals t.) Therefore if t is small, the p-th norms themselves much be well apart! After spending a few moments on the history of the inequality (as told to me by Ron Blei) we discussed what kind of extension do we need, and stated  the Bonami-Gross-Beckner inequality. We use Bonami’s inequality to proof of the inequality I(f) ≥ K t log t and briefly talked about what more does it give.

### Lecture 5

1) Review and examples. We reviewed what we did in the previous lecture and considered a few examples: Dictatiorship; the AND function (an opportunity to mention the uncertainty principle,) and MAJORITY on three variables. We also mentioned another connection between influences and Fourier-Walsh coefficients: for a monotone (non decreasing) Boolean function f, $I_k(f) = -2\hat f(\{k\})$.

2) KKL’s theorem

KKL’s theorem: There is an absolute constant K so that for every Boolean function f, with t=μ(f), there exists k, 1 ≤ k ≤ n such that $I_k(f) \ge K t (1-t) logn/n.$

To prove of KKL’s theorem: we repeat, to a large extent, the steps from Lecture 4 (of course, the proof of KKL’s theorem was where this line of argument came from.) We showed that if all individual influences are below $1/sqrt n$ than $I(f) \ge K t(1-t) \log n$.

We mentioned one corollary: For Boolean function invariant under a transitive group of permutations, all individual influences are equal and therefore $I(f) \ge K t (1-t)\log n$.

3) Further problems

In the  last part of the lecture we mentioned seven problems regarding influence of variables and KKL’s theorem (and I added two here):

1) What can be said about balanced Boolean functions with small total influence?

2) What can be said about Boolean functions for which I(f) ≤ K t log (1/t), for some constant K, where t=μ(f)?

3) What can be said about the connection between the symmetry group and the minimum total influence?

4) What can be said about Boolean functions (1/3 ≤ μ(f)≤ 2/3, say) for which $\max I_k(f) \le K log n/n$.?

5) What more can be said about the vector of influences $(I_1(f),I_2(f), \dots I_n(f))$?

6)* What is the sharp constant in KKL’s theorem?

7)* What about edge expansions of (small) sets of vertices in general graphs?

8) Under what conditions $I(f) \ge n^\beta$ for β >0.

9) What about influence of larger sets? In particular, what is the smallest t (as a function of n ) such that if $\mu(f)=t$ there is a set S of variables S ≤ 0.3n with $I_S(f) \ge 0.9$?

(This post  is a short version, I will add details later on.)

This entry was posted in Combinatorics, Computer Science and Optimization, Probability, Teaching and tagged , , . Bookmark the permalink.