We discussed two important examples that were introduced by Ben-Or and Linial: Recursive majority and tribes.
Recursive majority (RM): is a Boolean function with variables and . For the base case we use the majority function .
Tribes: Divide your n variables into s pairwise disjoint sets (“tribes”) of cardinality t. f=1 if for some tribe all variables equal one, and thus T=0 if for every tribe there is a variable with value ‘0’.
We note that this is not an odd function i.e. it is not symmetric with respect to switching ‘0’ and ‘1’. To have we need to set . We computed the influence of every variable to be C log n/n. The tribe function is a depth-two formula of linear size and we briefly discussed what are Boolean formulas and Boolean circuits (These notions can be found in many places and also in this post.).
I states several conjectures and questions that Ben-Or and Linial raised in their 85 paper:
Conjecture 1: For every balanced Boolean function with n variables there is a variable k whose influence is .
Conjecture 2: For every balanced Boolean function with n variables there is a set S of n/log n variables whose influence is 1-o(1).
Question 3: To what extent can the bound in Conjecture 2 be improved if the function f is odd. (Namely, .)
Our next theme was discrete isoperimetric results. I noted the connection between total influence and edge expansion and proved the basic isoperimetric inequality: If μ(f)=t then I(f) ≥ 4 t(1-t). The proof uses the canonical paths argument.
We proved using “compression” that sharp bound on I(f) as a function of t=μ(f). We made the analogy between compression and Steiner symmetrization – a classic method for proving the classical isoperimetric theorem. We discussed similar results on vertex boundary and on Talagrand-Margulis boundary (to be elaborated later in the course).
Then We proved the Harris-Kleitman inequality and showed how to deduce the fact that intersecting family of subsets of [n] with the property that the family of complements is also intersecting has at most sets.
The next topic is spectral graph theory. We proved the Hoffman bound for the largest size of an independent set in a graph G.
I mentioned graph-Laplacians and the spectral bound for expansions (Alon-Milman, Tanner)..
The proofs mentioned above are so lovely that I will add them on this page, but sometime later.
Next week I will introduce harmonic analysis on the discrete cube and give a Fourier-theoretic explanation for the additional log (1/t) factor in the edge isoperimetric inequality.
Important announcement: Real analysis boot camp in the Simons Institute for the Theory of Computing, is part of the program in Real Analysis and Computer Science. It is taking place next week on September 9-13 and has three lecture series. All lecture series are related to the topic of the course and especially: