Tag Archives: Boolean functions

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.)

Analysis of Boolean functions – week 2

Post on week 1; home page of the course analysis of Boolean functions

Lecture II:

We discussed two important examples that were introduced by Ben-Or and Linial: Recursive majority and  tribes.

Recursive majority (RM): F_m is a Boolean function with 3^m variables and F_{m+1} (x,y,z) = F_1(F_m(x),F_m(y),F_m(z)). For the base case we use the majority function F_1(x,y,z)=MAJ(x,y,z).

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 \mu=1/2 we need to set t=\log_2n - \log_2\log_2n+c. 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 \Omega (\log n/n).

Conjecture 2: For every balanced Boolean function with n variables there is a set S of n/log n variables whose influence I_S(f) is 1-o(1).

Question 3: To what extent can the bound in Conjecture 2 be improved if the function f is odd. (Namely, f(1-x_1,1-x_2,\dots, 1-x_n)=1-f(x_1,x_2,\dots, x_n).)

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.

Lecture III:

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 2^{n-2} 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:

Analysis of Boolean Functions – week 1

Home page of the course.

In the first lecture I defined the discrete n-dimensional cube and  Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets.

1) The largest possible intersecting family of subsets of [n];

2) The largest possible intersecting family of subsets of [n] so that the family of complements is also intersecting;

3) The largest possible family of graphs on v vertices such that each two graphs in the family contains a common triangle;

4) Chvatal’s conjecture regarding the maximum size of an intersecting family of sets contained in an ideal of sets;

5) Erdos-Ko-Rado Theorem.

Exercise: Prove one of the following

a) The Harris-Kleitman’s inequality

b) (from the H-K inequality) Every family of subsets of [n] with the property that every two sets have non-empty intersection and no full union contains at most 2^{n-2} sets.

More reading: this post :”Extremal combinatorics I: extremal problems on set systems“. Spoiler: The formulation of Chvatal’s conjecture but also the answer to the second exercise can be found on this post: Extremal combinatorics III: some basic theorems. (See also peoblen 25 in the 1972 paper Selected combinatorial research problems by Chvatal, Klarner and Knuth.)

feige

I moved to discuss the problem of collective coin flipping and the notion of influence as defined by Ben-Or and Linial. I mentioned the Baton-passing protocol, the Alon-Naor result, and Feige’s two-rooms protocol.

More reading: this post :” Nati’s influence“. The original paper of Ben-Or Linial:  Collective coin flipping, M. Ben-Or  and N. Linial, in “Randomness and    Computation” (S. Micali ed.) Academic Press, New York, 1989, pp.    91-115.

Ryan O’Donnell: Analysis of Boolean Function

Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and  he serializes it on a blog entiled Analysis of Boolean Function.  New sections appear on Mondays, Wednesdays, and Fridays.

Besides covering the basic theory, Ryan intends to describe applications in theoretical computer science and other areas of mathematics, including combinatorics, probability, social choice, and geometry.

Beside being a great place to learn this interesting material, actively participating in Ryan’s blog can make you a hero! Don’t miss this opportunity.

Each chapter of Ryan’s book ends with a “highlight” illustrating the use of Boolean analysis in problems where you might not necessarily expect it. In a post over Computational Complexity Ryan described some of these highlights in order to give a flavor of the contents:

  • Testing linearity (the Blum-Luby-Rubinfeld Theorem)
  • Arrow’s Theorem from Social Choice (and Kalai’s “approximate” version)
  • The Goldreich-Levin Algorithm from cryptography
  • Constant-depth circuits (Linial-Mansour-Nisan’s work)
  • Noise sensitivity of threshold functions (Peres’s Theorem)
  • Pseudorandomness for F_2-polynomials (Viola’s Theorem)
  • NP-hardness of approximately solving linear systems (Hastad’s Theorem)
  • Randomized query complexity of monotone graph properties
  • The (almost-)Polynomial Freiman-Ruzsa Theorem (i.e., Sanders’s Theorem)
  • The Kahn-Kalai-Linial Theorem on influences
  • The Gaussian Isoperimetric Inequality (Bobkov’s proof)
  • Sharp threshold phenomena (Friedgut and Bourgain’s theorems)
  • Majority Is Stablest Theorem
  • Unique Games-hardness from SDP gaps (work of Raghavendra and others)

Nati’s Influence

When do we say that one event causes another? Causality is a topic of great interest in statistics, physics, philosophy, law, economics, and many other places. Now, if causality is not complicated enough, we can ask what is the influence one event has on another one.  Michael Ben-Or and Nati Linial wrote a paper in 1985 where they studied the notion of influence in the context of collective coin flipping. The title of the post refers also to Nati’s influence on my work since he got me and Jeff Kahn interested in a conjecture from this paper.

Influence

The word “influence” (dating back, according to Merriam-Webster dictionary, to the 14th century) is close to the word “fluid”.  The original definition of influence is: “an ethereal fluid held to flow from the stars and to affect the actions of humans.” The modern meaning (according to Wictionary) is: “The power to affect, control or manipulate something or someone.”

Ben-Or and Linial’s definition of influence

Collective coin flipping refers to a situation where n processors or agents wish to agree on a common random bit. Ben-Or and Linial considered very general protocols to reach a single random bit, and also studied the simple case where the collective random bit is described by a Boolean function f(x_1,x_2,\dots,x_n) of n bits, one contributed by every agent. If all agents act appropriately the collective bit will be ‘1’ with probability 1/2. The purpose of collective coin flipping is to create a random bit R which is immune as much as possible against attempts of one or more agents to bias it towards ‘1’ or ‘0’. Continue reading