Preliminary definitions and Notations
First up, a list of preliminary notations and definitions of terms that recur throughout this blog post.
- denotes the -dimensional hypercube graph whose vertex set consists of all strings in and two vertices are adjacent iff the corresponding strings differ exactly in one-coordinate.
- For an undirected graph , the maximum degree of a vertex in is denoted by and denotes the largest eigenvalue of the adjacency matrix of .
- For and a subset of indices from , the string obtained from by flippling all entries of corresponding to the indices in is denoted by .
- Any function is called a boolean function.
Definition (Local sensitivity and sensitivity). Given a boolean function , the local sensitivity on the input , denoted by , is defined as the number of indices , such that , and the sensitivity of is .
Definition (Local block sensitivity and sensitivity). Given a boolean function , the local block sensitivity on the input , denoted by is defined as the maximum number of disjoint blocks of such that for each , and the block sensitivity of is .
The sensitivity conjecture and the tale of three theorems
(Sensitivity conjecture) There exists an absolute constant , such that for every boolean function , .
Sensitivity and block sensitivity are examples of complexity measures for boolean functions. Two complexity measures and are said to be polynomially related to each other if there exist polynomials such that for any Boolean function , we have and . The block sensitivity is known to be polynomially related to other complexity measures of boolean functions such as the degree (to be defined later). However, the question (a.k.a the sensitivity conjecture) of whether the block sensitivity is polynomially related to the sensitivity was posed as an open problem by Nisan and Szagedy in 1989 (Note that by a direct consequence of their definitons. The open problem was showing whether for some ). A few years later in 1992, Gotsman and Linial  showed the equivalence of the sensitivity conjecture to another open problem on the hypercube. Finally in 2019, Hao Huang resolved the sensitivity conjecture by leveraging on the equivalence shown by Gotsman and Linial.
Cue harmonic analysis on finite abelian groups
In lecture post 7 by Prof. Novak, we saw that is isomorphic to the group , i.e. bitstrings of length (Recall that denotes the subgroup of generated by the n disjoint transpositions Thus, a boolean function , can be identified with a member of the Hilbert space and the rich tools of harmonic analysis on discussed in lecture posts 7-9 are applicable to boolean functions. Note that the hypercube is the subgraph of the Caley graph of induced by the subgroup . Thus, the sensitivity conjecture can be rephrased in the language of induced subgraphs of the hypercube and this is exactly the essence of the work done by Gotsman and Linial in 1992.
Before we dive into the details, a few (post)-preliminary notations and remarks.
- Given an induced subgraph of , let denote the subgraph of induced on the vertex set .
- For , the function is defined as , with the convention that for all where denotes the empty set.
- In lecture post 7 (and also in the qual exam) we saw that the functions (which exactly correspond to the characters of since is isomorphic to ) form an orthogonal basis for under the inner product .
- Thus, given a boolean function , by Fourier expansion, can be written as , where denotes the Fourier coefficients.
- The average of a boolean function on is denoted as . Note that since for all , we have the identity which is quite useful when proving theorem 1 (see below).
Definition. Given a boolean function , the degree of is defined as .
Theorem 1 [Gotsman and Linial]. The following two statements are equivalent for any monotone strictly increasing function .
a. For any induced subgraph of with , we have .
b. For any boolean function , we have that .
Gotsman and Linial show that proving the equivalence of statements a and b above is equivalent to proving the equivalence of yet another two statements and then proceed to prove this second equivalence.
Proof of Theorem 1. First, we show the equivalence of statement a to following statement a’:
a’. For any boolean function , implies there exists an input such that .
a’ implies a : Given an induced subgraph of , it can be associated with a corresponding boolean function defined such that iff . By a direct consequence of the definitions of adjacency in and the local sensitivity of for and for (Note that here denotes the degree of the vertex in the subgraph and is not to be confused with the degree of a boolean function that was defined earlier). Thus, . Let denote the average value of on , i.e. . Note that implies . Thus, statement a’ implies .
a implies a’ : Given a boolean function , define to be the subgraph induced by the set of vertices . By an identical arument as in the previous paragraph, . Also, implies . Thus, statement a implies thereby showing the equivalent of statements a and a’.
Now, we show the equivalence of statement b to statement b’:
b’. For any boolean function , implies .
Assuming b and that the premise for b’ is true, then and since is assumed to be monotonic strictly increasing this shows that and thus b implies b’. Now, towards showing the other implication let denote a boolean function with degree . Assume without loss of generality that for . Now, consider the function defined as . By construction and , i.e has full degree as a boolean function on . Now, the contrapositive of b’ says that implies . Thus, and this finshes showing the equivalence of b and b’.
Thus, proving theorem 1 has been reduced to the task of proving the equivalence of statements a’ and b’. Now, given a boolean function , define another boolean function where is the parity function of . Note that . Thus,
Thus, for all , . Also note that for all , because every bit flip which causes a change in value of does not cause a change in function value of and vice-versa. Thus, where denotes the empty set.
a’ implies b’: Towards a contradiction assume that and . This by definition implies and thus . By a’, there exist a such that and since this implies there exists a such that which contradicts the premise that .
b’ implies a’: Again towards a contradiction assume that given such that we have that for all . Since this implies that which by 2′ implies . Note that is equivalent to and thus which contradicts the premise that and this completes the proof of theorem 1.
Theorem 2 [Huang] . For every integer , let be an arbitrary -vertex induced subgraph of , then
The proof of theorem 2 is going to be the main focus for the remainder of this blogpost but before that we discuss two corollaries which show why theorem 2 resolves the sensitivity conjecture.
Corollary 1. For every boolean function , .
Proof of Corollary 1. For any induced subgraph of with , since the total number of vertices in is , either contains atleast vertices or does. So without loss of generality, assume contains atleast vertices (If not, just replace with in the remainder of the proof). Now, theorem 2 (along with the fact that the maximum degree is non-decreasing in the number of vertices in ) implies . Let and note that it is a monotone strictly increasing function on . Now, theorem 1 implies and this completes the proof.
Theorem 3 [Tal]. For every boolean function , .
It should be noted that theorem 3 is an imporvement on the work by Nisan and Szegedy in 1992 wherein they showed that .
Corollary 2. For every boolean function , .
Note that corollary 2 follows immediately from theorem 3 and corollary 1. Thus, corollary 2 confirms the sensitivity conjecture by showing that the block sensitivity and the sensitivity of a boolean function are indeed polynomially related.
Cue matrix analysis – “A proof that came straight from THE Book”
In this section, we will focus on Hao Huang’s proof of theorem 2. The core chunk of the proof invovles a creative construction of an iterative sequence of matrices whose instance is closely related to the adjacency matrix of and an application of Cauchy’s interlace theorem which is stated as follows,
(Cauchy’s interlace theorem) Let be a symmetric , be a principal submatrix of for some . If the eigenvalues of are , and the eigenvalues of are , then for all ,
Recall that we saw in Math 202A that Cauchy’s interlace theorem can be proven via a direct application of the Courant-Fischer theorem.
Now, we move on to the iterative matrix sequence that turns out to be a bite-sized kryptonite for the sensitivity conjecture. Consider the sequence of symmetric square matrices defined iteratively as follows,
The first exercise is to study the spectrum of and the second exercise is to compute an upper bound for the largest eigenvalue of a specific type of matrix. These two exercises then set us up nicely for a clever application of Cauchy’s interlace theorem to prove theorem 2.
a) Show that where denotes the identity matrix.
b) Show that the trace of is .
c) Conclude that the eigenvalues of are with multiplicity and with multiplicity .
Exercise 2. Suppose is a -vertex undirected graph and is a symmetric matrix whose entries are in , and whose rows and columns are indexed by the vertex set of . Also assume whenever and are non-adjacent vertices in . Then show that
The defintion of this iterative sequence of matrices is not without precedent. Note that the adjacency matrix of can also be defined in a similarly iterative manner. Recall that a vertex of is a string in . Given a -length string of -1s and 1s it naturally extends to exactly two strings in and these two -strings correspond to the only two vertices of whose corresponding strings have their first entries to be the same as the original string (note that these two vetices of are adjacent). Exapnding on this observation, the hypercube can be thought of as having two sub-hypercubes with a perfect matching connecting these two subcubes. In otherwords, consider the following sequence of iteratively defined matrices,
Then represents the adjacency matrix of and in particular, note that is equal to the matrix obtained by changing every entry of to .
Now that we have all the necessary ingredients, let’s discuss the proof of Theorem 2.
(Restated) Theorem 2 [Huang] . For every integer , let be an arbitrary -vertex induced subgraph of , then
Proof of Theorem 2 [Haung].
Let be the sequence of matrices that we defined above and let be a -vertex induced subgraph of . Note that naturally induces a principal submatrix of (written with respect to an appropriate permutation of the standard basis). As discussed in the preceeding paragraph, by changing every entry of to 1, we get the adjacency matrix of . So, in particular, and satisfy the conditions of the statement in Exercise 2 and thus,
Also, since is a principal submatrix of the matrix , by Cauchy’s interlace theorem,
From Exercise 1, we know that the eigenvalues of are with multiplicity and with multiplicity . Thus, and thus,
and this completes the proof.
I will end this blog post for our Math 202C class with a quote from Scott Aaronson’s blog post about Hao Huang’s proof of the sensitivity conjecture.
Paul Erdös famously spoke of a book, maintained by God, in which was written the simplest, most beautiful proof of each theorem. The highest compliment Erdös could give a proof was that it “came straight from the book.” In this case, I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this.-Scott Aaronson
The funny thing is, a few days after Prof. Aaronson’s blogpost, his former student Shalev Ben-David posted in the comments section, a simplication of Huang’s proof which does not use Cauchy’s interlacing theorem.
Anyways, talking about the sensitivity conjecture is indeed quite a fitting end to the Math 202 series since both, Gotsman & Linial’s work and Hao Huang’s work on this 30 year old ex-open problem utilize almost exclusively, concepts which we have studied over the past three quarters.
Thanks for reading my post and have a great summer everyone!
-  Huang, H. (2019). Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3), 949-955.
-  N. Nisan, M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity, 4 (1992), 462–467.
-  C. Gotsman, N. Linial, The equivalence of two problems on the cube, J. Combin.Theory Ser. A, 61 (1) (1992), 142–146.
-  F. Chung, Z. F¨uredi, R. Graham, P. Seymour, On induced subgraphs of the cube, J. Comb. Theory, Ser. A, 49 (1) (1988), 180–187.
-  A. Tal, Properties and applications of boolean function composition, Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ITCS ’13, 441–454.
-  Karthikeyan, Rohan & Sinha, Siddharth & Patil, Vallabh. (2020). On the resolution of the sensitivity conjecture. Bulletin of the American Mathematical Society. 57. 1. 10.1090/bull/1697.
-  https://www.scottaaronson.com/blog/?p=4229
-  Lecture notes for Math 202A by Prof. Philip Gill.
-  D. Kroes, J. Naranjo, J. Nie, J. O’ Neill, N. Seiger, S. Spiro, E. Zhu, Linear Algebra methods in Combinatorics, ABACUS notes Fall 2019 UCSD.