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 [2] 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.
Exercise 1.
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.
Closing Remarks
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!
References
- [1] Huang, H. (2019). Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3), 949-955.
- [2] N. Nisan, M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity, 4 (1992), 462–467.
- [3] C. Gotsman, N. Linial, The equivalence of two problems on the cube, J. Combin.Theory Ser. A, 61 (1) (1992), 142–146.
- [4] 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.
- [5] A. Tal, Properties and applications of boolean function composition, Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ITCS ’13, 441–454.
- [6] 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.
- [7] https://www.scottaaronson.com/blog/?p=4229
- [8] Lecture notes for Math 202A by Prof. Philip Gill.
- [9] 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.