on Huang's sensitivity conjecture proof

Overview

Huang proved the sensitivity conjecture by proving a sharp spectral statement about induced subgraphs of the Boolean cube (Huang, 2019). The combinatorial statement is remarkably short: every induced subgraph of $Q_n$ on more than half of the vertices has maximum degree at least $\sqrt{n}$ as a real lower bound. Through the reduction of Gotsman and Linial (Gotsman & Linial, 1992), this gives

$$s(f)\ge \sqrt{\mathrm{deg}(f)}$$

for every Boolean function $f$. Equivalently,

$$\mathrm{deg}(f)\le s(f{)}^2.$$

The proof is a single linear-algebraic construction: sign the adjacency matrix of the hypercube so that its square is $nI$, then use eigenvalue interlacing on a principal submatrix.

The statement above uses no heavy machinery, but it sits at the intersection of Boolean function complexity and extremal graph theory. The sensitivity conjecture was posed in the framework of Nisan and Szegedy’s study of Boolean functions as real polynomials (Nisan & Szegedy, 1994). The missing link was whether sensitivity is polynomially related to the other standard decision-tree measures. Huang’s theorem gives the clean bound

$$\mathrm{deg}(f)\le s(f{)}^2,$$

and this is enough to close the polynomial-equivalence question.

Since vertex degrees are integers, the induced-subgraph conclusion implies maximum degree at least $\lceil \sqrt{n}\rceil$ when one wants an integral statement. In the proof it is more natural to keep the spectral lower bound $\sqrt{n}$.

Boolean Function Measures

Let

$$f:\{0,1{\}}^n\to \{0,1\}$$

be a Boolean function. Every such function has a unique multilinear real polynomial representation

$$f(x)=\sum _{S\subseteq [n]}{a}_S\prod _{i\in S}{x}_i.$$

The degree is

$$\mathrm{deg}(f)=\max \{|S|:a_S\ne 0\}.$$

For $x\in \{0,1{\}}^n$ and $i\in [n]$, let $x^{\oplus i}$ be obtained from $x$ by flipping the $i$th coordinate. The sensitivity of $f$ at $x$ is

$$s(f,x)=\left|\{i\in [n]:f(x^{\oplus i})\ne f(x)\}\right|,$$

and the sensitivity of $f$ is

$$s(f)=\underset{x\in \{0,1{\}}^n}{\max }s(f,x).$$

The sensitivity conjecture originally asked for a polynomial relation between sensitivity and block sensitivity. For this note, the useful equivalent target is the degree form

$$\mathrm{deg}(f)\le s(f{)}^C$$

for an absolute constant $C$. Huang proves this with $C=2$.

The Cube Form of the Theorem

Let $Q_n$ be the $n$-dimensional hypercube graph. Its vertices are $\{0,1{\}}^n$, and two vertices are adjacent if they differ in exactly one coordinate. For a subset $S\subseteq \{0,1{\}}^n$, write $Q_n[S]$ for the subgraph induced by $S$.

Huang's induced-subgraph theorem

If $S\subseteq \{0,1{\}}^n$ satisfies

$$|S|>2^{n-1},$$

then

$$\Delta (Q_n[S])\ge \sqrt{n}.$$

Here $\Delta$ is maximum degree. The theorem improves the earlier logarithmic lower bound of Chung, Furedi, Graham, and Seymour for induced subgraphs of the cube (Chung et al., 1988). Huang’s proof is not a refinement of that argument; it is a different spectral certificate.

The rest of the note proves this theorem first, then explains why it implies the sensitivity theorem.

Signed Adjacency Matrices

A signed adjacency matrix of a graph is a symmetric matrix whose off-diagonal entries are $0,\pm 1$, with a nonzero entry exactly when there is an edge. Huang constructs a signed adjacency matrix $A_n$ for $Q_n$ satisfying the decisive identity

$$A_n^2=n{I}_{2^n}.$$

The construction is recursive. Start with

$$A_1=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$$

Assuming $A_{n-1}$ has been constructed, define

$$A_n=\left(\begin{array}{cc}{A}_{n-1}& I\\ I& -A_{n-1}\end{array}\right).$$

This matrix is indexed by splitting $Q_n$ into the two copies of $Q_{n-1}$ given by the last coordinate. The two diagonal blocks sign the edges inside the two copies, and the identity blocks sign the matching edges between corresponding vertices in the two copies. Therefore $A_n$ is indeed a signed adjacency matrix of $Q_n$.

Now compute the square. If $A_{n-1}^2=(n-1)I$, then

$$A_n^2=\left(\begin{array}{cc}{A}_{n-1}^2+I& A_{n-1}-A_{n-1}\\ A_{n-1}-A_{n-1}& I+A_{n-1}^2\end{array}\right)=\left(\begin{array}{cc}nI& 0\\ 0& nI\end{array}\right)=nI.$$

Thus, by induction,

$$A_n^2=nI$$

for every $n$.

This identity determines the spectrum. If $\lambda$ is an eigenvalue of $A_n$, then ${\lambda }^2=n$, so

$$\lambda \in \{\sqrt{n},-\sqrt{n}\}.$$

Since $A_n$ has zero diagonal,

$$\mathrm{tr}(A_n)=0.$$

The trace is also the sum of eigenvalues. Therefore the multiplicities of $\sqrt{n}$ and $-\sqrt{n}$ are equal, and each has multiplicity $2^{n-1}$.

Interlacing on a Large Principal Submatrix

Let

$$N=2^n,m=|S|.$$

The induced signed adjacency matrix on $S$ is the principal submatrix

$$A_S=A_n[S,S].$$

Let the eigenvalues of $A_n$ be ordered as

$${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_N.$$

Since $A_n$ has $2^{n-1}$ eigenvalues equal to $\sqrt{n}$, we have

$${\lambda }_1=\cdots ={\lambda }_{2^{n-1}}=\sqrt{n}.$$

Let the eigenvalues of $A_S$ be

$${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_m.$$

Cauchy’s interlacing theorem gives

$${\lambda }_i\ge {\mu }_i\ge {\lambda }_{i+N-m}(1\le i\le m).$$

Taking $i=1$ gives

$${\mu }_1\ge {\lambda }_{1+N-m}.$$

Because $m>2^{n-1}$,

$$N-m<2^{n-1},$$

and hence

$$1+N-m\le 2^{n-1}.$$

Therefore

$${\lambda }_{1+N-m}=\sqrt{n},$$

so

$${\mu }_1\ge \sqrt{n}.$$

Thus the largest eigenvalue of the signed induced adjacency matrix $A_S$ is at least $\sqrt{n}$.

From Eigenvalue to Degree

Let $v$ be a real eigenvector of $A_S$ for the eigenvalue ${\mu }_1$. Choose a vertex $x\in S$ for which $|v_x|$ is maximal. Since $v$ is nonzero, $|v_x|>0$.

The eigenvalue equation at coordinate $x$ is

$$(A_{S}v{)}_x={\mu }_1{v}_x.$$

The left side is a signed sum over the neighbors of $x$ that remain inside $S$:

$$(A_{S}v{)}_x=\sum _{\begin{array}{c}y\in S\\ y\sim x\end{array}}{\sigma }_{xy}{v}_y,$$

where each sign ${\sigma }_{xy}$ is $\pm 1$. Taking absolute values,

$${\mu }_1|v_x|=\left|\sum _{\begin{array}{c}y\in S\\ y\sim x\end{array}}{\sigma }_{xy}{v}_y\right|\le \sum _{\begin{array}{c}y\in S\\ y\sim x\end{array}}|v_y|.$$

By maximality of $|v_x|$,

$$|v_y|\le |v_x|$$

for every $y\in S$. Hence

$$\sum _{\begin{array}{c}y\in S\\ y\sim x\end{array}}|v_y|\le {\mathrm{deg}}_{Q_n[S]}(x)|v_x|.$$

Combining these inequalities gives

$${\mu }_1|v_x|\le {\mathrm{deg}}_{Q_n[S]}(x)|v_x|.$$

Canceling $|v_x|>0$ yields

$${\mathrm{deg}}_{Q_n[S]}(x)\ge {\mu }_1\ge \sqrt{n}.$$

This proves Huang’s induced-subgraph theorem.

The Gotsman—Linial Reduction

We now derive the sensitivity theorem from the induced-subgraph theorem. Let $f:\{0,1{\}}^n\to \{0,1\}$ have degree $d$.

First reduce to the full-degree case. Choose a degree-$d$ monomial

$$\prod _{i\in T}{x}_i,|T|=d,$$

with nonzero coefficient in the multilinear polynomial for $f$. Fix all coordinates outside $T$ arbitrarily. The restricted function

$$h:\{0,1{\}}^T\to \{0,1\}$$

still has degree $d$, because no monomial of larger degree can alter the coefficient of ${\prod }_{i\in T}{x}_i$. Also

$$s(h)\le s(f),$$

because every sensitive coordinate of $h$ is a sensitive coordinate of $f$ at the corresponding full input. Thus it is enough to prove

$$s(h)\ge \sqrt{d}.$$

After relabeling, we may assume from now on that $h$ is a Boolean function on $d$ variables with

$$\mathrm{deg}(h)=d.$$

For notational simplicity write $n=d$ in the next paragraphs.

Define the parity function

$$\mathrm{par}(x)=x_1\oplus x_2\oplus \cdots \oplus x_n,$$

and define

$$g(x)=h(x)\oplus \mathrm{par}(x).$$

The key point is that $g$ is not balanced.

To see this cleanly, switch to the $\{\pm 1\}$ representation. Let

$$H(x)=(-1{)}^{h(x)}.$$

The degree of $H$ as a multilinear polynomial in the cube characters is the same as the degree of $h$, since $H=1-2h$ after an affine change of coordinates. Therefore the top Fourier coefficient of $H$ is nonzero:

$$\hat{H}([n])=2^{-n}\sum _{x\in \{0,1{\}}^n}H(x)(-1{)}^{x_1+\cdots +x_n}\ne 0.$$

But

$$H(x)(-1{)}^{x_1+\cdots +x_n}=(-1{)}^{h(x)+\mathrm{par}(x)}=(-1{)}^{g(x)}.$$

Thus

$$\sum _x(-1{)}^{g(x)}\ne 0.$$

This means that $g$ takes the values $0$ and $1$ unequal numbers of times. Let $S$ be the larger level set of $g$, so

$$|S|>2^{n-1}.$$

By Huang’s induced-subgraph theorem, $Q_n[S]$ has a vertex $x$ with at least $\sqrt{n}$ neighbors inside $S$.

Now compare $g$ and $h$ across an edge. If $y$ is a neighbor of $x$, then

$$\mathrm{par}(y)=\mathrm{par}(x)\oplus 1.$$

If also $x,y\in S$, then $g(x)=g(y)$. Therefore

$$h(x)\oplus \mathrm{par}(x)=h(y)\oplus \mathrm{par}(y)=h(y)\oplus \mathrm{par}(x)\oplus 1.$$

Canceling $\mathrm{par}(x)$ in ${\mathbb{F}}_2$ gives

$$h(y)=h(x)\oplus 1.$$

Thus every edge from $x$ to a neighbor inside $S$ is sensitive for $h$. Since there are at least $\sqrt{n}$ such neighbors,

$$s(h)\ge \sqrt{n}.$$

Returning to the original function $f$, we get

$$s(f)\ge s(h)\ge \sqrt{d}=\sqrt{\mathrm{deg}(f)}.$$

Equivalently,

$$\mathrm{deg}(f)\le s(f{)}^2.$$

This is the sensitivity theorem.

Sharpness

The exponent $2$ cannot be improved in this degree-versus-sensitivity form. Let $n=m^2$ and define

$$f(x)=\underset{i=1}{\overset{m}{\bigwedge }}\underset{j=1}{\overset{m}{\bigvee }}{x}_{ij}.$$

Each OR block has real degree $m$, and the AND of the $m$ blocks multiplies the leading terms, so

$$\mathrm{deg}(f)=m^2.$$

The sensitivity is $m$. Indeed, if each block contains exactly one $1$, then $f=1$, and flipping any one of those $m$ ones changes the output to $0$. Conversely, changing a single bit affects only one block, and the worst cases expose at most one sensitive bit per block or all $m$ bits in one all-zero block, so

$$s(f)=m.$$

Therefore

$$\mathrm{deg}(f)=s(f{)}^2.$$

The Mechanism

Huang’s proof isolates the only difficult point in the conjecture. The Gotsman—Linial reduction converts degree into imbalance after twisting by parity. Imbalance gives a set occupying more than half of the cube. The signed adjacency matrix then converts that density condition into an eigenvalue lower bound. Finally, the elementary maximum-coordinate argument converts the eigenvalue lower bound into an ordinary unsigned degree lower bound.

The striking feature is that the signs make the cube behave like a matrix square root of $nI$. Without signs, the ordinary adjacency matrix of $Q_n$ has many eigenvalues and no such principal-submatrix obstruction at the half-cube threshold. The recursive block matrix

$$A_n=\left(\begin{array}{cc}{A}_{n-1}& I\\ I& -A_{n-1}\end{array}\right)$$

is precisely the device that creates the two-point spectrum $\{\pm \sqrt{n}\}$ while keeping the support equal to the edges of the cube.

🐻  Chung, F.R.K., Füredi, Z., Graham, R.L. & Seymour, P.D. 1988. On induced subgraphs of the cube. Journal of Combinatorial Theory, Series A 49(1), 180–187.

🐻  Gotsman, C. & Linial, N. 1992. The equivalence of two problems on the cube. Journal of Combinatorial Theory, Series A 61(1), 142–146.

🐻  Huang, H. 2019. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Annals of Mathematics 190(3), 949–955.

🐻  Nisan, N. & Szegedy, M. 1994. On the degree of Boolean functions as real polynomials. Computational Complexity 4(4), 301–313.